# Course:Fall 2007 Exercises 4

This is the fourth set of exercise problems for the Fall 2007 introductory course.

The solutions are due in class on Friday, November 9. Up to two problems (and any extra-credit problems) may be submitted on Wednesday, November 14. (Mention on your Friday submission which ones you are postponing.)

1. Malleability and CCA Security. Let f be a one-to-one function (other than the identity function) such that f can be computed in polynomial time. Then we call an encryption scheme Enc malleable with respect to f if there is a way to efficiently compute $\mathsf{Enc}(f(m))$ from $\mathsf{Enc}(m)$, for any message m. (This is not the "real" definition of malleability, but is sufficient here). Note that f need not be easy to invert.
1. [5 pts] Is the ElGamal encryption scheme malleable? If so, then for what class of functions f is it malleable (give the most general class you can)? If not, show that malleability is impossible.
2. [10 pts] Show that if an encryption scheme is malleable with respect to some f, then it is not CCA secure. Give an attack/adversary and explicitly show how it violates either SIM-CCA or IND-CCA definition.
2. Preimage collision resistance and second-preimage collision resistance are incomparable. In this problem we consider hash functions on a finite domain (from {0,1}n(k) to {0,1}k). (Also see problem 3.4 below.)
1. [5 pts] Suppose $\mathcal{H}$ is preimage collision resistant. Modify $\mathcal{H}$ to $\mathcal{H}'$ (possibly with a different domain), so that the latter remains preimage collision resistant, but is not second-preimage collision resistant. (Prove these properties of $\mathcal{H}'$.)
3. (Shrinking) CRHF implies OWF. For this problem, we say that "x has a collision under f" if there exists an $x' \ne x$ such that f(x) = f(x').
1. [15 pts] Let $\mathcal{H}$ be a CRHF and suppose that for every $h\in\mathcal{H}$ and every x, x has a collision under h. Show that the function f(h,x) = (h,h(x)) is a OWF.
2. [10 pts] Now suppose that for each $h\in\mathcal{H}$, all but a negligible fraction of x's have a collision under h. Show that the function f(h,x) = (h,h(x)) is a OWF.
3. [10 pts] Show that if $\mathcal{H}$ is a CRHF from n bits to n / 2 bits, then the function f(h,x) = (h,h(x)) is a OWF.
4. [10 pts] Given a CRHF from n bits to n − 2 bits, construct a CRHF $\mathcal{H}$ from n bits to n − 1 bits, such that the function f(h,x) = (h,h(x)) is not a OWF.
4. Domain Extension of MAC using UOWHF.
1. [5 pts] Given a MAC scheme $(\mathsf{KeyGen},\mathsf{MAC},\mathsf{Ver})$, with $\mathsf{MAC}:\{0,1\}^{n(k)}\rightarrow\{0,1\}^k$ and UOWHF $\mathcal{H}$ (with domain {0,1} * ), describe another MAC scheme with domain {0,1} * . Do describe all three algorithms for the scheme.
2. [15 pts] Give the reduction for showing that the new scheme is secure if both the original MAC and the UOWHF are secure. That is, given an adversary A with a non-negligible advantage against the new MAC scheme, give two adversaries, A1 for the original MAC scheme and A2 for the UOWHF such that at least one of them has non-negligible advantage.
5. [15 pts] Insecurity of CBC-MAC for variable length inputs. Recall the CBC-MAC construction, which constructs a MAC for nt-bit messages (for some fixed n) from a PRF with input and output being t-bit blocks. (To compute $\mathsf{CBCMAC}_K$, we split the nt-bit message into t-bit blocks $(m_1, \ldots, m_n)$, and then compute $y_0 = 0^t\,$, $y_i = \mathsf{PRF}_K(y_{i-1} \oplus m_i)$. The output is $y_n\,$.) This CBC-MAC is secure for messages of length exactly tn. Show that this CBC-MAC is insecure when used on messages having length any multiple of t (not just tn for a fixed $n\,$). To show this, construct an adversary that queries a CBC-MAC oracle with one or more messages whose lengths are multiples of t, and succeeds in producing a forged signature (with probability 1), possibly on a message of a different length.
6. (Extra credit.) Pitfalls in fiddling with CCA secure schemes. To protect against packet corruptions while transmission, suppose one uses an "enhanced" encryption scheme $(\mathsf{Gen},\mathsf{Enc}^*,\mathsf{Dec}^*)$, derived from an encryption scheme $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ as follows. The ciphertext in the enhanced scheme consists of three ciphertexts independently generated as encryptions of the plaintext under the original scheme. i.e., $\mathsf{Enc}^*(m)=(c_1,c_2,c_3)$, where $c_i\leftarrow\mathsf{Enc}(m)$. For decryption, the three ciphertexts are decrypted. If at least two of the ciphertexts decrypt to the same message, that message is output as the decryption. Otherwise an error message is produced.
1. Show that $(\mathsf{Gen},\mathsf{Enc}^*,\mathsf{Dec}^*)$ is IND-CPA secure, if $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ is.
2. Show that $(\mathsf{Gen},\mathsf{Enc}^*,\mathsf{Dec}^*)$ is not IND-CCA secure, even if $(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})$ is.