# 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$$.
where $$\oplus$$ denotes the bitwise exclusive-or (XOR) of two binary strings. Since \begin{align*} \mathsf{Dec}_k(\mathsf{Enc}_k(m)) &= k \oplus (k \oplus m) \\ &= (k \oplus k) \oplus m \\ &= \{0\}^\ell \oplus m \\ &= m \end{align*}

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}$$:

1. $$\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)$$.
2. $$\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.