# One-Time Pad

Mort Yao# 1 Construction

**One-time pad (Vernam cipher).** Given \(\ell \in \mathbb{Z}^+\) which is the fixed length of the plaintext, define the following encryption scheme \(\Pi=(\mathsf{Gen},\mathsf{Enc},\mathsf{Dec})\):

- Message space \(\mathcal{M} = \{0,1\}^\ell\).
- Key space \(\mathcal{K} = \{0,1\}^\ell\).
- Ciphertext space \(\mathcal{C} = \{0,1\}^\ell\).
- \(\mathsf{Gen}\) outputs a key \(k \in \mathcal{K}\) according to the uniform distribution.
- \(\mathsf{Enc}\) takes as input a key \(k \in \mathcal{K}\) and a message \(m \in \mathcal{M}\), and outputs the ciphertext \(c := k \oplus m\).
- \(\mathsf{Dec}\) takes as input a key \(k \in \mathcal{K}\) and a ciphertext \(c \in \mathcal{C}\), and outputs the message \(m := k \oplus c\).

this encryption scheme satisfies the correctness requirement.

# 2 Secrecy and Cryptanalysis

**Theorem 2.1.** One-time pad is perfectly secret.

**Proof.**For any \(c \in \mathcal{C}\) and \(m \in \mathcal{M}\), \[\begin{align*} \Pr[C=c | M=m] &= \Pr[\mathsf{Enc}_K(m) = c] \\ &= \Pr[m \oplus K=c] \\ &= \Pr[K=m \oplus c] \\ &= 2^{-\ell} \end{align*}\]

where the last equality holds since the key \(K\) is a uniform \(\ell\)-bit string.

Fix any distribution over \(\mathcal{M}\). For any \(c \in \mathcal{C}\), we have \[\begin{align*} \Pr[C=c] &= \sum_{m' \in \mathcal{M}} \Pr[C=c | M=m'] \cdot \Pr[M=m'] \\ &= 2^{-\ell} \cdot \sum_{m' \in \mathcal{M}} \Pr[M=m'] \\ &= 2^{-\ell} \end{align*}\] Using Bayesâ€™ Theorem: \[\begin{align*} \Pr[M=m | C=c] &= \frac{\Pr[C=c | M=m] \cdot \Pr[M=m]}{\Pr[C=c]} \\ &= \frac{2^{-\ell} \cdot \Pr[M=m]}{2^{-\ell}} \\ &= \Pr[M=m] \end{align*}\]Therefore, the one-time pad encryption scheme is perfectly secret.

■

*Remark 2.2.* In the proof of Theorem 2.1 (perfect secrecy of one-time pad), we assumed that \(\Pr[K = m \oplus c] = 2^{-\ell}\). If the key \(K\) is not a independently, uniformly chosen \(\ell\)-bit string, the equality does not hold. In practice, for the one-time pad to be perfectly secure, it is required that a one-time key is used for each encryption. If the same key is used more than once (in multiple sessions of encryption), then perfect secrecy cannot be guaranteed.

Theoretically, the one-time pad scheme is unbreakable under any cryptanalysis (as long as the key is uniformly chosen every time). When the key is reused, the resulting scheme is sometimes called a *two-time pad* and it is vulnerable to frequency analysis or other kinds of heuristic attacks. Notice that an adversary who obtains \(c = k \oplus m\) and \(c' = k \oplus m'\) can compute \[c \oplus c' = (k \oplus m) \oplus (k \oplus m') = m \oplus m'
\] which is the bitwise exclusive-or of the two messages.

**Theorem 2.3.** One-time pad does not yield indistinguishable multiple encryptions in the presence of an eavesdropper.

**Proof.** In a multiple-message eavesdropping experiment \(\mathsf{PrivK}^\mathsf{mult}\) where a random bit \(b\) is chosen, consider the following polynomial-time adversary \(\mathcal{A}\):

- \(\mathcal{A}\) outputs \(\vec{M}_0 = (m_{0,1}, m_{0,2}) = (\{0\}^\ell, \{0\}^\ell)\) and \(\vec{M}_1 = (m_{1,1}, m_{1,2}) = (\{0\}^\ell, \{1\}^\ell)\).
- \(\mathcal{A}\) receives \(\vec{C} = (c_1, c_2)\) which contains two ciphertexts.
- If \(c_1 = c_2\), \(\mathcal{A}\) outputs \(b' = 0\).
- Otherwise, \(\mathcal{A}\) outputs \(b' = 1\).

Let \(k\) be the reused key. It is known that \(k \oplus m_{0,1} = k \oplus m_{0,2}\) and \(k \oplus m_{1,1} \neq k \oplus m_{1,2}\). Clearly, \(c_1 = c_2\) if and only if \(b=0\), otherwise \(b=1\). Therefore, the adversary \(\mathcal{A}\) will output \(b'=b\) correctly with probability \(1\).

■

**Theorem 2.4.** One-time pad is not CPA-secure.

**Proof.** Given any pair of plaintext and ciphertext \((m, c)\), the adversary computes \[m \oplus c = m \oplus (k \oplus m) = k
\] which is the key.

■

As shown by Theorem 2.4, it is extremely simple to recover the key used in one-time pad under any attack where an attacker can obtain the plaintext and the ciphertext at the same time (e.g., KPA, CPA, CCA). However, this is rarely a concern in reality, since the one-time key is never supposed to be reused.