Homework 1

1. [Exercise 2.7] When using the one-time pad with the key k = 0^l, we have Enc_k(m) = k ⊕ m = m and the message is sent in the clear! It has therefore been suggested to modify the one-time pad by only encrypting with k! = 0^l (i.e., to have Gen choose k uniformly from the set of nonzero keys of length l). Is this modified scheme still perfectly secret? Explain. Note  ⊕  is XOR.
2. Prove (or refute) that we may assume that the key-generation algorithm Gen always chooses a key uniformly from the key space 𝕂.
   • Hint: What the problem means is that even when the actual algorithm Gen does not follow a uniform distribution, one can still assume it follows a uniform distribution, without changing the security of encryption scheme.
   • Updates: You should first decide if the problem statement is true. If it is true, prove it. If not, find a counter-example.
3. [Bonus:30/100] [Exercise 3.4]: Prove the equivalence of Definition 3.8 and Definition 3.9.

Homework 2

1. [Exercise 3.20]: Consider a stateful variant of CBC-mode encryption where the sender simply increments the IV by 1 each time a message is encrypted (rather than choosing IV at random each time). Show that the resulting scheme is not CPA-secure.
2. Prove or refute that chained CBC, as shown in Figure 3.8 in the textbook, is not CPA-secure.
3. Merkle tree collision-resistance [Exercise 5.12] Prove theorem 5.11, that is, the collision-resistance of Merkle tree depends on the collision-resistance of the hash function used in Merkle tree.
   • Hint: Consider the case that the message input to the Merkle tree is of fixed number of blocks.
4. Merkle tree for variable-length hash [Exercise 5.13] Show how to find a collision in the Merkle tree construction if t is not fixed. Specifically, show how to find two sets of inputs x₁, ..., x_t and x₁′, ..., x_2t′, such that MT_t(x₁, ..., x_t) = MT_2t(x₁′, ..., x_2t′).
   • Can you design a fix of the problem and have a secure variable-length collision resistant Merkle tree?