1. [2 points] State whether the following encryption scheme is perfectly secret or not.
Justify your answer either with a proof or a counterexample.
The message space is M = {0, . . . , 4}. Algorithm Gen chooses a uniform key from
the keyspace {0, . . . , 5}. Enck(m) = (k + m) mod 5 and Deck(c) = (c − k) mod 5.
2. [2 points] Consider a variant of the one-time pad with message space ={0, 1}
l and
keyspace K restricted to all l-bit strings with an even number of 1’s. Is this scheme
perfectly secret? Justify your answer either with a proof or a counterexample.
3. [2 points] Let negl1 be a negligible function. Prove that for any positive polynomial
p, the function negl2 defined by negl2
(n) = p(n) · negl1
(n) is negligible.
4. [4 points] Let G : {0, 1}
n → {0, 1}
l(n) be a pseudorandom generator with expansion
factor l(n) n. Assume that G is defined for all n ≥ 1. Prove that G1 defined below
is a pseudorandom generator where |s| denotes the length of s, |s| ≥ 2, and si
is the
ith bit of s.
G1(s) = G(s1, s2, . . . , s|s|−1)ks|s|
.
