1. Consider an encryption scheme, where the plaintext and ciphertext are n-bit strings. The key generation algorithm works as follows: generate a n2 -bit random string s (assume n is even) and the key is k = sks (where k is concatenation). Encryption and decryption work exactly as one-time pad c = m ⊕ k and m = c ⊕ k. a) Can this scheme be perfectly secret? b) What is the probability of an adversary winning the indistinguishability game? 2. Let f and g be negligible functions and p be any positive polynomial. a) Prove that the function p(n) · f(n) is a negligible function. b) Prove that 1 ( f(1n) + g(1n)) is a negligible function. 3. Let G0, G1 be two different pseudorandom generators where jG0(s)j = jG1(s)j. Prove that no efficient distinguisher can detect wheter it is given a pseudorandom string output by G0 or a pseudorandom string output by G1. In other words, prove that, for any PPT algorithm D, there is a negligible function negl such that Pr[D(G0(s)) = 1] − Pr[D(G1(s)) = 1] ≤ negl(n) where both probabilities are taken over uniform choice of s 2 f0; 1gn and the randomness of D. [Hint: Use triangle inequality \jx + yj ≤ jxj + jyj for any real numbers x; y 2 R".] 4. (3.6) Let G be a pseudorandom generator where jG(s)j 2jsj. If G0 is defined as follows, State and Justify whether they are necessarily pseudorandom generator or not? a) Define G0(s) = G(s1 · · · sn=2), where s = s1 · · · sn. b) Define G0(s) = G(sjj1jsj). c) Define G0(s) = G(s), where s is the bitwise complement of s
