# Exercises

- Page ID
- 7316

1.1: The one-time pad encryption of plaintext “mario” (written in ASCII) under key \(k\) is:

1000010000000111010101000001110000011101

What is the one-time pad encryption of “luigi” under the same key?

1.2: Alice is using one-time pad and notices that when her key is the all-zeroes string \(k = 0^{\lambda}\), then \(\text{Enc(}k, m) = m\) and her message is sent in the clear! To avoid this problem, she decides to modify KeyGen to choose a key uniformly from \(\{0, 1\}^{\lambda}\ \{0^{\lambda}\}\). In this way, her plaintext is never sent in the clear.

Does Claim 1.3 still hold with respect to this modified one-time pad? Prove or disprove.

1.3: When Alice encrypts the key k itself using one-time pad, the ciphertext will always be the all-zeroes string! So if an eavesdropper sees the all-zeroes ciphertext, she learns that Alice encrypted the key itself. Does this contradict Claim 1.3? Why or why not?

1.4: Describe the flaw in this argument:

Consider the following attack against one-time pad: upon seeing a ciphertext c, the eavesdropper tries every \(k\in ?\) until she has found the one that was used, at which point she outputs the plaintext \(m\). This contradicts the argument in Section 1.3 that the eavesdropper can obtain no information about m by seeing the ciphertext.

1.5: Suppose Alice encrypts two plaintexts m and m’ using one-time pad with the same key \(k\). What information about \(m\) and \(m\)’ is leaked to an eavesdropper by doing this (assume the eavesdropper knows that Alice has reused \(k\))? Be as specific as you can!

1.6: Suppose we modify the subroutine discussed in Claim 1.3 so that it also returns \(k\):

\[\underline{\text{CTXT'}(m\in \{0,1\}^{\lambda}):}\\\space\space k\space\leftarrow\space\{0,1\}^{\lambda}\\\space\space\text{return}\space(k,k\oplus m)\nonumber\]

Is it still true that for every m, the output of \(\text{CTXT’} (m)\) is distributed uniformly in \((\{0,1\}^{\lambda})^2\)?

1.7: In this problem we discuss the security of performing one-time pad encryption twice:

(a). Consider the following subroutine that models the result of applying one-time pad encryption with two *independent* keys:

\[\underline{\text{CTXT'}(m\in \{0,1\}^{\lambda}):}\\\space\space k_1\space\leftarrow\space\{0,1\}^{\lambda}\\\space\space k_2\space\leftarrow\space\{0,1\}^{\lambda}\\\space\space\text{return}\space k_2\oplus (k_1\oplus m)\nonumber\]

Show that the output of this subroutine is uniformly distributed in \(\{0,1\}^{\lambda}\)

(b). What security is provided by performing one-time pad encryption twice with *the same key*?

1.8: Show that the output of the following subroutine is uniformly distributed in \(\mathbb{Z}_n\):

\[\underline{\text{CTXT'}(m\in \mathbb{Z}_n):}\\\space\space k\space\leftarrow\space \mathbb{Z}_n\\\space\space\text{return}\space(k + m)\% n\nonumber\]