Exercises

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$