## Homework 1

- [Exercise 2.7] When using the one-time pad with the key k = 0
^{l}, we have *E**n**c*_{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 *G**e**n* choose k uniformly from the set of nonzero keys of length l). Is this modified scheme still perfectly secret? Explain. Note ⊕ is XOR.
- Prove (or refute) that we may assume that the key-generation algorithm
*G**e**n* always chooses a key uniformly from the key space 𝕂.
- Hint: What the problem means is that even when the actual algorithm
*G**e**n* 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.

- [Bonus:30/100] [Exercise 3.4]: Prove the equivalence of Definition 3.8 and Definition 3.9.

## Homework 2

- [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.
- Prove or refute that chained CBC, as shown in Figure 3.8 in the textbook, is not CPA-secure.
*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.

*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*_{1}, ..., *x*_{t} and *x*_{1}′, ..., *x*_{2t}′, such that *M**T*_{t}(*x*_{1}, ..., *x*_{t}) = *M**T*_{2t}(*x*_{1}′, ..., *x*_{2t}′).
- Can you design a fix of the problem and have a secure variable-length collision resistant Merkle tree?