Description

1. Consider an encryption scheme, where the plaintext and ciphertext are n-bit strings. The key generation algorithm works as follows: generate a -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 is a negligible function.
3. Let G0, G1 be two different pseudorandom generators where |G0(s)| = |G1(s)|.
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
negl(n)
where both probabilities are taken over uniform choice of s ∈ {0,1}n and the randomness of D.
[Hint: Use triangle inequality “|x + y| ≤ |x| + |y| for any real numbers x,y ∈ R”.]
4. (3.6) Let G be a pseudorandom generator where |G(s)| > 2|s|. 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(s||1|s|).
c) Define G0(s) = G(s), where s is the bitwise complement of s
1