Course:Fall 2006 Exercises 1

From CRYPTUTOR

This is the first set of exercises for the Fall 2006 introductory course.

The solutions are due in class on Friday, September 15.

Below, the message space is denoted by ${\mathcal M}$ , the key space by ${\mathcal K}$ and the ciphertext space by ${\mathcal C}$ . $\mathsf{Enc}:{\mathcal K}\times{\mathcal M} \rightarrow {\mathcal C}$ will be the encryption algorithm in a Private-key encryption scheme.

Exercises on Perfect Secrecy of (Private-key) Encryption

Let be some set of N elements. Let . Arrange the elements of in a circle, and define, for and , to be the element of which is places clockwise from in the circle.
1. [5 pts] Show that $\mathsf{Enc}:(k,m)\mapsto \mathsf{Clockwise}_k(m)$ yields a perfectly secret one-time encryption scheme.
2. [5 pts] Can you think of a set ${\mathcal M}$ and a circular ordering for its elements, so that $\mathsf{Clockwise}_k(m)$ can be calculated efficiently (i.e., in $O(\mathsf{poly}(\log N))$ time)? For extra credit, can this be extended to work efficiently on all possible circular orderings? Elaborate.
3. [5 pts] Note that above, ${\mathcal C}={\mathcal M}$ , and that for any given $k$ , the function $\mathsf{Enc}(k,\cdot)$ is a permutation. For perfect secrecy, does the former always imply the latter? Can you think of a situation where these conditions do not hold?
[10 pts] Prove that $\mathsf{Enc}$ is perfectly secret if and only if it is SIM-onetime secure.
[20 pts] Prove that $\mathsf{Enc}$ is perfectly secret, if and only if, for all distributions over the message space $\mathcal M$ , the ciphertext distribution is the same. That is, for any two distributions ${\mathcal T}_{\mathcal M}$ and ${\mathcal V}_{\mathcal M}$ , the distributions $\{ \mathsf{Enc}(k,m)\}_{k\leftarrow\mathcal K;m\leftarrow {\mathcal T}_{\mathcal M} }$ and $\{ \mathsf{Enc}(k,m)\}_{k\leftarrow\mathcal K;m\leftarrow {\mathcal V}_{\mathcal M} }$ are identical.
[15 pts] For $\mathsf{Enc}$ to be perfectly secret, show that we require $|{\mathcal K}|\ge|{\mathcal M}|$ .
Consider a "two-message encryption scheme" .
1. [5 pts] Define perfect secrecy for such an encryption.
2. [5 pts] Let $\mathcal M = \mathcal K = \mathcal C$ be the set of $n$ -bit strings. Let $\mathsf{Enc}^2(k,m_1,m_2) = (k\oplus m_1,k \oplus m_2)$ , where $\oplus$ is bit-wise xor-ing. Prove that this is not perfectly secret, according to your definition.
3. [10 pts] Define perfect simulatability for $\mathsf{Enc}^2$ . Modify this definition to argue that the only information leaked by the above encryption scheme is $m_1\oplus m_2$ .
(Extra Credit Problem)Recall the definitions of SIM-onetime security and IND-onetime security. Now consider a modification of IND-onetime, which we will call 3IND-onetime. In this variant, the adversary outputs 3 messages, , we choose a random and send an encryption of . The adversary outputs , and its advantage is defined now as .
1. Show that if Enc is $\epsilon\,$ -SIM-onetime secure, then it is also $\epsilon\,\!$ -3IND-onetime secure.
2. What is the best $\epsilon'\,$ for which you can show that $\epsilon\,\!$ -IND-onetime security implies $\epsilon'\,\!$ -3IND-onetime security? Show this by assuming there exists a 3IND-onetime adversary with advantage $\epsilon'\,\!$ and use it to construct a IND-onetime adversary with advantage $\epsilon\,\!$ .
3. Does $\epsilon\,\!$ -3IND-onetime security imply $\epsilon'\,\!$ -SIM-onetime security? If so, then what is the best $\epsilon'\,\!$ you can show? Give proof either way.

More Exercises on Security Definitions of (Private-key) Encryption

[10 pts] Consider two distributions ${\mathcal T}_{\mathcal C}$ and ${\mathcal V}_{\mathcal C}$ over some space ${\mathcal C}$ . Show that if ${\mathcal T}_{\mathcal C}\neq{\mathcal V}_{\mathcal C}$ , then there is a boolean function, $A\,\!$ on ${\mathcal C}$ (i.e., $A:{\mathcal C}\rightarrow\{0,1\}$ ) such that $\mathrm{Pr}_{c\leftarrow{\mathcal T}_{\mathcal C}}[A(c)=1]\neq \mathrm{Pr}_{c\leftarrow{\mathcal V}_{\mathcal C}}[A(c)=1]$ . How large can you make the difference $\mathrm{Pr}_{c\leftarrow{\mathcal T}_{\mathcal C}}[A(c)=1]- \mathrm{Pr}_{c\leftarrow{\mathcal V}_{\mathcal C}}[A(c)=1]$ ? (This quantity equals a measure of distance between the two distributions ${\mathcal T}_{\mathcal C}$ and ${\mathcal V}_{\mathcal C}$ , called the statistical difference.)
[10 pts] Recall the definitions of IND-CPA and SIM-CPA given in the class. Show that there is an environment in the SIM-CPA definition such that for any given adversary and simulator, the difference $\mathrm{Pr}[z_{\mathrm{ REAL}}]-\mathrm{Pr}[z_{\mathrm{IDEAL}}]\,\!$ equals the advantage of that adversary in the IND-CPA experiment. With your environment, does it matter how the simulator behaves?