Yes, the one-time pad model provides the technical notion of IND-CPA security. An adversary's advantage at the IND-CPA game is zero if the pad is uniform random. This is a standard—and, once you get past the definitions, trivial!—lemma on the way to proving an IND-CPA security theorem for a practical stream cipher like Salsa20 or AES-CTR.
Of course, real-world adversaries have powers like forgery, not just eavesdropping, and—cost of pad management aside—the one-time pad model does nothing to defend against forgery! You really want an authenticated cipher, and maybe even a nonce-misuse-resistant authenticated cipher. But this question is about IND-CPA security only.
One-time pad model.
You and your partner in international espionage share a very long uniform random pad $p$ consisting of a sequence of pages $p_1, p_2, \dots, p_n$, in order to exchange a sequence of messages $m_1, m_2, \dots, m_n$ about overthrowing inconveniently democratically elected governments.
To send a message $m_i$, you peel a page $p_i$ off the pad and affix the ciphertext $c_i := m_i \oplus p_i$ to the leg of a pigeon. (Because pigeons do not provide reliable in-order transport, you may want to scrawl the number $i$ on the fragment of paper you have affixed to the pigeon's leg.)
Your partner in diplomacy, on return of the pigeon, then decrypts $c_i$ by peeling $p_i$ off their copy of the pad and recovering $m_i = c_i \oplus p_i$.
You then eat the page of the pad you just used (or burn it if you're too squeamish to be a real spy like in the good old movies—make sure to mix the ashes thoroughly in a glass of water when you're done).
We model this by having the sender and receiver keep state about how many pages of the pad they have used: $$\require{cancel}\cancel{\!p_1\!\!},
\cancel{\!p_2\!\!}, \cancel{\!p_3\!\!}, \cancel{\!p_4\!\!}, \,p_5, \,p_6, \,p_7,$$ or equivalently by just remembering the number $i$ of messages that have been exchanged so far.
Aside: With a stream cipher like Salsa20, we simply choose $p_i := \operatorname{Salsa20}_k(i)$ where $k$ is a uniform random 256-bit key shared by the sender and receiver—everything else is the same (ciphertext is $c_i := m_i \oplus p_i = m_i \oplus \operatorname{Salsa20}_k(i)$, decryption is $c_i \oplus \operatorname{Salsa20}_k(i)$, sender and receiver must remember $i$, must not repeat $i$, etc.), except that you don't have to fumble around with pads of paper or eat them.
Chosen-plaintext attack (-CPA).
In a chosen-plaintext attack setting, we assume the adversary can learn the ciphertexts of plaintexts they choose. We model this by furnishing the adversary with a subroutine called an encryption oracle. When the adversary queries the encryption oracle for a message, the oracle returns a ciphertext for the message.
- The oracle may be nondeterministic—it may roll dice to decide which of many valid ciphertexts to return, e.g. to choose a CBC initialization vector.
- The oracle may be stateful—it may remember what past queries the adversary submitted, what its answers were, or just how many queries there have been so far.
If the oracle is deterministic and stateless, as in AES-GCM-SIV with a fixed nonce, then we cannot have ciphertext indistinguishability per se—at best only indistinguishability of ciphertexts for nonrepeated messages.
(Some textbooks consider only the nondeterministic case, which is curious because the two most popular stream ciphers on the planet today, AES-CTR and ChaCha as used in TLS 1.3's AES-GCM and ChaCha/Poly1305 cipher suites, use state! This doesn't mean that AES-GCM and ChaCha/Poly1305 fail to provide IND-CPA security; it just means the textbook's definition was limited—stateful IND-CPA notions are widely used in the literature.)
def ..._cpa_...(adversary):
k = generate_key()
i = [0]
def encryption_oracle(plaintext):
iv = random_iv() # may be nondeterministic
ciphertext = encrypt(k, iv, i)
i[0] += 1 # may be stateful
return ciphertext
... adversary(encryption_oracle) ...
Distinguishing game, or indistinguishability (IND-).
In the distinguishing game, the adversary's goal is to find a pair of messages $\hat m_0 \ne \hat m_1$ such that, if I flip a coin giving outcome $b \in \{0,1\}$ and return the encryption of the message $\hat m_b$, the adversary can tell with probability nonnegligibly above 1/2 which way the coin toss $b$ came up. The messages $\hat m_0$ and $\hat m_1$ may depend on the answers the encryption oracle gave.
We'll formally split the adversary into two stages:
$A_0$ or adversary[0]
is given an encryption oracle to query, and returns a pair of messages $m_0$ and $m_1$ it would like to be challenged with;
$A_1$ or adversary[1]
is given the encryption of $m_b$ for a secret coin toss $b$, and returns a guess about what $b$ was.
def ind_cpa_...(adversary):
k = generate_key()
i = [0]
def encryption_oracle(plaintext):
iv = random_iv() # may be nondeterministic
ciphertext = ..._encrypt(k, iv, i[0], plaintext)
i[0] += 1 # may be stateful
return ciphertext
# First, give the adversary a chance to query encryption
# oracle; let them pick two messages for the challenge.
m0, m1 = adversary[0](encryption_oracle)
# Choose which of the messages to challenge them with.
b = flip_coin()
mb = m1 if b else m0
# Challenge the adversary to guess what b was.
b_ = adversary[1](encryption_oracle(mb))
# Return whether the adversary guessed right or not.
return b == b_
The adversary's distinguishing advantage is the absolute difference between the probability that they guess right and the probability that they guess wrong. In semiformal math jargon,
\begin{equation}
\operatorname{Adv}^{\operatorname{IND-CPA}}_E(A)
:= \left|\Pr[\operatorname{IND-CPA}_E(A) = 1] - \Pr[\operatorname{IND-CPA}_E(A) = 0]\right|.
\end{equation}
Here $E$ represents the encryption scheme (encrypt
), $A$ represents the adversary (adversary
), and $\operatorname{IND-CPA}_E(A)$ means playing the IND-CPA game with $E$ (ind_cpa_...
) against the adversary $A$.
IND-CPA game for one-time pad model.
Just fill in the empty lines:
def ind_cpa_otp(adversary):
npages = 1000 # let's try to conserve paper
pad = generate_pad(npages)
i = [0]
def encryption_oracle(plaintext):
# multi-page messages left as exercise for reader
ciphertext = plaintext ^ pad[i]
pad[i[0]] = None # om nom nom
i[0] += 1 # next page, please
return ciphertext
m0, m1 = adversary[0](encryption_oracle)
b = flip_coin()
mb = m1 if b else m0
b_ = adversary[1](encryption_oracle(mb))
return b == b_
Lemma.
If the pages $p_i$ of the pad $p$ are independent uniform random, then $$\operatorname{Adv}^{\operatorname{IND-CPA}}_{\operatorname{OTP}_p}(A) = 0.$$
Proof. Suppose the adversary submits $q$ queries to the encryption oracle. Then the challenge ciphertext is $m_b \oplus p_{q+1}$. The distribution of $m_0 \oplus p_{q+1}$ and the distribution of $m_1 \oplus p_{q+1}$ are both uniform, and are independent of all prior ciphertexts and of $b$, so the distribution of the adversary's answers is independent of $b$; hence $\Pr[A_1(m_b \oplus p_{q+1}) = b] = 1/2$ and thus $\operatorname{Adv}^{\operatorname{IND-CPA}}_{\operatorname{OTP}_p}(A) = 0.$
When you instantiate the model in practice by choosing $p_i = \operatorname{Salsa20}_k(i)$ or $p_i = \operatorname{AES}_k(i)$ for a short uniform random key $k$, the adversary gains a small advantage at winning the IND-CPA game—but it is bounded by their advantage at distinguishing Salsa20 or AES from a uniform random function.
Theorem.
If the PRF advantage against a function family $F_k$ for uniform random $k$ is bounded by $\varepsilon$, then the IND-CPA advantage against the one-time pad model above instantiated with $p_i = F_k(i)$ is bounded by $\varepsilon$.
Proof. Playing the IND-CPA game against any adversary, with an oracle $\mathcal O(i)$ to generate the pad $p_i$ (generate_pad
), serves as a PRF distinguisher for $\mathcal O = F_k$ for a uniform random key $k$ vs. $\mathcal O = R$ for a uniform random function $R$. Since the IND-CPA advantage when $\mathcal O = R$ is zero by the lemma, the IND-CPA advantage when $\mathcal O = F_k$ can't be better than the bound $\varepsilon$ on the PRF advantage against $F_k$.
See, e.g., [1], Lemma 12, in which $p_i = R(i)$ for a uniform random function $R$ in $\operatorname{CTR}[R]$ (equivalent to the one-time pad model); and Theorem 13, in which $p_i = F_k(i)$ for a pseudorandom function family $F$ such as Salsa20 with uniform random key $k$ in $\operatorname{CTR}[F]$—this is the standard reference for the security of ‘CTR mode’ of a block cipher.
The paper uses a slightly different game, in which the coin toss $b$ happens up front and all queries to the oracle are two distinct messages; the result is a technically slightly stronger theorem but the practical consequences are essentially the same. Note: The ‘XOR’ scheme in the paper is different—instead of going through the pad sequentially (with state), it picks pages of the pad uniformly at random for each message (with nondeterminism), so there's a danger of collision that grows quadratically in the number of messages. The proof of Lemma 12 is more circuitous than necessary because the authors chose to prove a theorem about the ‘XOR’ scheme first, which required setting bounds on collision probabilities.
For a longer exposition, see Goldwasser & Bellare's lecture notes[2], §§6.4–6.7.
This is the design inspiration for stream ciphers like Salsa20 and AES-CTR: you can focus all your effort on a method to generate pads from a short shared secret key, like Salsa20 or AES, which have had decades of work poured into them by the smartest cryptanalysts in the world; then the nice and simple operation xor takes care of combining a pad with a message to keep the message confidential from eavesdroppers. (See, e.g., the Salsa20 design paper[3], p. 4, ‘Should encryption and decryption be different?’.) The rules for safe usage of Salsa20 and AES-CTR are derived from the rules for safe usage of a one-time pad: just as you must not reuse a page of your pad for two different messages, you must not reuse a Salsa20 or AES-CTR nonce with the same key for two different messages.