Exercise 1

(30 points) A student was bothered by one aspect of the EAV-game. She finds it unnatural that the adversary produces two messages m0 , m1, only one of which is encrypted.  She thinks it would be more natural if the adversary were to produce just a single message m, and then be unable to distinguish between an encryption of m and an encryption of a fixed “junk” message.   She argues that this means encrypting a message m (of the attacker’s choice) completely hides m, because it looks like an encrypted“junk”message that obviously has nothing to do with m .

To reflect this intuition, the student defines the ZERO game between an adversary  and a cryptosystem Π = (Gen, Enc, Dec), which proceeds as follows:

1.  is given the security parameter 1n, then produces a message m  ∈  {0, 1}∗ (of arbitrary length).

2. The game generates k ← Gen(1n ) and a ciphertext C ← Enck(mˆ), where in the “real world”, mˆ is defined to be mˆ = m, and in the “ideal world” mˆ = 0|m|, that is, the all-zeros (junk) message of the same length as m .

3.  is given the ciphertext C and ultimately either accepts (indicating that it thinks it is in the real world) or rejects (indicating that it thinks it is in the ideal world).

The advantage of  in the ZERO game against Π is defined as

AdvΠ(Z)ERO () = l Pr [  in “real world”accepts]− Pr [  in “ideal world”accepts] l.     Finally, we say that Π is ZERO-secure if any p.p.t. (Probabilistic Polynomial Time) adver-

sary  has only negligible advantage in the ZERO game against Π .  Prove that ZERO- security is equivalent to EAV-security.

Exercise 2

(30 points) For each of the following symmetric-key encryption schemes, state the strongest of the following security definitions that it necessarily satisfies: (2) chosen-plaintext (CPA) security, (1) EAV security, or (0) neither of these. In all cases, the key-generation algorithm Gen(1n ) outputs a uniformly random key k ← {0, 1}n .

Give some sound intuition why the scheme satisfies the definition you identified, though you do not need to give a formal proof. If applicable, also show that the scheme does not necessarily satisfy the next-strongest definition, by giving an efficient adversary that has non-negligible advantage in the corresponding game. Also, recall that (Init, NextBit) is a secure stream cipher, Init takes in an initialization vector, and outputs an initial state; St0, and NextBit(Sti) = (Sti+1, y); i.e. it outputs an updated state and a bit y .

(a)  Enck(m  ∈ {0, 1}∗) lets St0  =  Init(k) and generates a string p  ∈ {0, 1}|m|  by iterating NextBit starting from St0, where (Init, NextBit) is a secure stream cipher.  It outputs ciphertext C = m ⊕ p .

(b)  Enck(m ∈ {0, 1}3n ) chooses random r ← {0, 1}n and outputs ciphertext

C = (r, (G(r)∥k) ⊕ m),

where G is a PRG with stretch l (n) = 2n .

(c)  Enck(m ∈ {0, 1}n ) lets p ∥k\  = G(k) for p, k\  ∈ {0, 1}n  where G is a PRG with stretch l (n) = 2n, outputs ciphertext c = m ⊕ p, and replaces k with k\ for the next call (so

Enc is stateful).

Exercise 3

(20 points) Prove the converse of the following theorem, which was proved in class:       Theorem:   Given a cryptosystem Π = (Gen, Enc, Dec) and PRG G with expansion factor l (n) > n where:

1. Gen generates a uniformly random string k from {0, 1}n, when given 1n as input.

2.  Enc(m, k) outputs c := m ⊕ G(k),

3.  Dec(c, k) outpus m := c ⊕ G(k).

If G is secure, then this cryptosystem is EAV-secure.

The converse statement (which you are required to prove) is: If G is not a secure PRG, then the above cryptosystem is not EAV-secure.

Hint: Recall that the attacker can be a randomized algorithm.

Exercise 4

(10 points) In this problem, we will show that the existence of PRFs, implies the existence of PRGs.  Prove that if F is a length-preserving PRF (that is, output length equals input length), then G(s) = Fs(1)∥Fs(2)∥ · · · ∥Fs(l) is a PRG with expansion factor l · n .