# Course:Fall 2007 Exercises 1

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

The solutions are due in class on Friday, September 14. (At most one of the 5 problems, as well as the extra credit problems, can be submitted later, on Wednesday, September 19.)

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

1. [10 pts] For $\mathsf{Enc}$ to be perfectly secret and correct, show that we require $|{\mathcal K}|\ge|{\mathcal M}|$.
2. [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.
3. Equivalence of SIM-onetime security, IND-onetime security and perfect secrecy.
1. [15 pts] To complete the proof from Lecture 2 that $\mathsf{Enc}$ is perfectly secret and correct if and only if it is SIM-onetime secure, show that if $\mathsf{Enc}$ is not perfectly secret then it is not SIM-onetime secure.
2. [15 pts] Prove that $\mathsf{Enc}$ is perfectly secret if and only if it is IND-onetime secure.
3. [Extra Credit.] Prove (directly, without using perfect secrecy) that $\mathsf{Enc}$ is correct and IND-onetime secure if and only if it is SIM-onetime secure.
4. Consider a "two-message encryption scheme" $\mathsf{Enc}^2 :{\mathcal K}\times{\mathcal M} \times \mathcal M \rightarrow {\mathcal C} \times \mathcal C$.
1. [2 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. [8 pts] How would you define SIM-twice security? Modify this definition to argue that the only information leaked by the above encryption scheme is $m_1\oplus m_2$.
5. IND-onetime security is in terms of the advantage the adversary gets in guessing a message given the ciphertext (compared to when it gets nothing). Consider creating such a definition for the following scenario: the message comes from a fixed distribution over ${\mathcal M}$. (Eve does not have any influence on the choice of the message, but she knows this distribution).
1. [2 pts] Suppose Eve does not receive any input, but wants to output a guess for the message so that her probability of getting it right is maximized. What should her strategy be (in terms of the message distribution)? What is the maximum probability of her guessing the message correctly?
2. [2 pts] Use this to suggest a modified (relaxed) version of IND-onetime security definition for this case. (Hint: There are two changes to be made: in the way the message to be encrypted is chosen, and in defining the advantage.)
3. [1 pts] Also suggest a modification of SIM-onetime security definition for the setting when the message is known to come from a fixed distribution. (Hint: Involves one change.) [Extra Credit: Argue that an encryption scheme satisfying the modified definition will still satisfy the original SIM-onetime security definition, but for a modified message space.]
4. The goal of this exercise is to show that not having an advantage is not the same as not having any extra information.
1. [10 pts] Give an encryption scheme and a message distribution so that it satisfies the modified IND-onetime security, but does not satisfy the modified SIM-onetime security. (Hint: Consider the example of imperfect encryption scheme from Lecture 1, with an appropriate message distribution. Be sure to prove your claims.)
2. [10 pts] Show that the modified SIM-onetime security definition does imply the modified IND-onetime security definition (for the same message distribution).