9
$\begingroup$

If we're considering Chosen-Plaintext Attack setting, then the adversary has access to the Encryption Oracle right, and we know that OTP is only considered secure if we use the key only once. How would we ensure that the adversary uses the key only once?

Or would it not matter how the adversary uses the encryption oracle since in the end they will be presented with a ciphertext corresponding to a plaintext not queried and the adversary would not be able to decrypt it because they don't know the key. Making it CPA-Secure. Is this second train of thought the correct way to think about OTP in CPA setting?

Thank you!

$\endgroup$
  • 3
    $\begingroup$ I'm not sure the idea of a CPA even applies to an OTP. $\endgroup$ – cpast May 16 '15 at 20:20
9
$\begingroup$

Note: In this answer, I stick to a definition of the One Time Pad where the random pad is used only One Time; at least, I've the name of it as support! Otherwise, it is well known that the OTP encryption scheme consisting of XOR with a repeated key is insecure by even the weakest standard (unknown plaintext with redundancy).

Late addition: further, I stick to the definition of IND-CPA given for ciphers in standard literature and quoted below. See this other answer for a different definition, which applies to the OTP, and is met.

INDistinguishability under Chosen Plaintext Attack applies to encryption schemes; there's no way the OTP can be made to match the definition of an encryption scheme, thus the formal definition of IND-CPA does not apply to the OTP.

Specifically, the OTP does not fit definition 3.7 in Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography, first edition (CRC Press, 2008):

A private-key encryption scheme is a tuple of probabilistic polynomial-time algorithms ($\text{Gen}$, $\text{Enc}$, $\text{Dec}$) such that: (..)

  1. The key-generation algorithm $\text{Gen}$ takes as input the security parameter $1^n$ and outputs a key $k$; (..)
  2. The encryption algorithm $\text{Enc}$ takes as input a key $k$ and a plaintext message $m\in\{0,1\}^*$, and outputs a ciphertext $c$. (..)
  3. The decryption algorithm $\text{Dec}$ takes as input a key $k$ and a ciphertext $c$, and outputs a message $m$. (..)

It is required that for every $n$, every key $k$ output by $\text{Gen}(1^n)$, and every $m\in\{0,1\}^*$, it holds that $\text{Dec}_k(\text{Enc}_k(m))=m$.

where $\{0,1\}^*$ is the set of all (finite-length) binary strings.

There's no way the OTP can fit this framework:

  • If we try to assimilate the random pad and the key, we hit the problem that in the above definition the same $k$ can be used for several messages (and further that some messages can be larger than the key, but that's secondary); the OTP does not allow that (due to the One Time requirement of OTP).

  • If we try to fit the random pad into $\text{Enc}$, and still keep the ciphertext as it is in the OTP (including, of the same size as the message), then we have no way to build a working $\text{Dec}$.

Note: some practical encryption schemes use message spaces deviating from $\{0,1\}^*$, like the set of all bytestrings up to some size, or even a fixed-size bytestring, perhaps even shorter than the key (which is common in block ciphers); and it is accepted to twist the definition of an encryption scheme to allow that. However it is an essential point of any encryption scheme that the total size of plaintext enciphered with a given key is allowed to increase significantly above the size of the key; again, the OTP does not allow that.

$\endgroup$
  • 1
    $\begingroup$ As I see it, the only problem of the OTP in respect to the formal definition of encryption schemes is that the message space is not $\{0,1\}^*$. If you relax the definition to allow encryption schemes with a different message space, then the OTP is one, and the concept of CPA-security applies. What's a "cipher"? $\endgroup$ – fkraiem May 17 '15 at 9:07
  • 1
    $\begingroup$ @fkraiem: even if we restrict the message space of a cipher to $\{0,1\}^{|k|}$, the OTP does not fit that definition of a cipher, because a cipher must allow encryption of multiple messages with the same key, and the OTP does not. $\endgroup$ – fgrieu May 17 '15 at 9:47
  • $\begingroup$ @fgrieu I'm not sure what you mean by "cipher"? Nevertheless, OTP can be used for the encryption of multiple messages with the same key. However, it would not be secure. You can liken the way OTP is used (different key each time) to the way certain modes of encryption, such as Output Feedback Mode, work. Output Feedback Mode is CPA-Secure and thus the logic should extend to OTP. Don't think about the OTP as using a different key each time, think of it as using a different section of the long key each time (Basically synchronized encryption where state is maintained). $\endgroup$ – Gordon May 17 '15 at 9:57
  • 1
    $\begingroup$ @Gordon: I (now) see what you mean. If we consider that the OTP allows key reuse then, yes, it is a cipher (perhaps, by a variation of the above definition where the plaintext size is restricted), but not a secure one under even the weakest definition of security (unknown plaintext with known redundancy). On the other hand, two of out three words in the name One TIme Pad are there to emphasize that the pad/key can not be reused, so this twists the definition of OTP. $\endgroup$ – fgrieu May 17 '15 at 10:03
  • 1
    $\begingroup$ ... We should be able fix the first issue by making the keyspace $\{0,1\}^*$ and restricting the total length of messages that can be encrypted with each key to a polynomial function of $n$. This seems reasonable enough, since the adversary can only make a polynomial number of queries anyway. But the statefulness issue remains, although I guess we could just make the keys long enough compared to the maximum total message length to make the probability of overlap negligible. Lots of handwaving here, I admit, but it seems like it should work. $\endgroup$ – Ilmari Karonen May 19 '15 at 18:18
4
$\begingroup$

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.

  1. 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.

  2. 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$.

  3. 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.

$\endgroup$
  • $\begingroup$ Exactly. The OTP model does nothing against forgery, and that is a major weakness. So I wonder whether we have more options than UMAC. $\endgroup$ – Patriot Aug 22 at 16:06
  • $\begingroup$ Would the downvoter care to explain what you disagreed with in this post? $\endgroup$ – Squeamish Ossifrage Aug 22 at 18:55
  • $\begingroup$ Didn't downvote(Actually upvoted) but I find "the one-time pad model does nothing to defend against forgery!" a bit puzzling... was there ever the claim of the contrary? In any sensible exposition of the OTP, it is used in a modular step to understand how to build a secure channel. So the security claims of OTP are only with respect to confidentiality. And usually it is assumed that it is used on top of an authenticated channel... So yes, it might be a futile exercise to just study confidentiality in isolation since we understand now AEADs but there's nothing wrong to only look at OTP alone... $\endgroup$ – Marc Ilunga Aug 28 at 21:31
  • $\begingroup$ @MarcIlunga I did that so that no passersby would be misled into thinking that meeting the standard of IND-CPA security is sufficient in real-world applications. It is a common misconception—perhaps not here but elsewhere—that an adversary who doesn't know the pad is somehow prevented from forging messages. It is a common novice mistake to focus on the OTP model and secrecy as the paragon of security, neglecting everything else involved like authentication. So while it isn't germane to the question per se, it may be helpful to understand the context of the question in cryptography. $\endgroup$ – Squeamish Ossifrage Aug 28 at 21:37
  • $\begingroup$ I see, But I feel like OTP questions are always answered with the hidden assumption that the person asking is a 'novice' that doesn't know anything about the role confidentiality does and doesn't play in the process of constructing a secure channel. Which can be a bit frustrating. And I don't think everything should be about real-world applications. It should maybe be allowed to as curiosity question as long as the context is very clear.. Now I understand that the risk is that a developer takes an answer here out of context and implements something broken but maybe we need to find a balance... $\endgroup$ – Marc Ilunga Aug 28 at 21:58
2
$\begingroup$

Ciphertext indistinguishability under CPA is equivalent to semantic security. Semantic security is the computational complexity analogue to Shannon's concept of perfect secrecy. OTP is perfectly secure, therefor is CPA secure.

Under CPA, the adversary will be presented with a ciphertext corresponding to a plaintext queried (the adversary chose the plaintext) but will not be able to distinguish it from the ciphertext corresponding to other plaintext.

$\endgroup$
2
$\begingroup$

When we talk about IND-CPA, we always assume that the encryption scheme is under same-key usage. Why do not we consider the "IND-CPA" of an encryption scheme which is under multiple-key usage? Because the notion "IND-CPA" is equivalent to "IND-EAV" in this case.

I try to explain my view by using the definition in Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography, first edition (CRC Press, 2008):

A private-key encryption scheme is a tuple of probabilistic polynomial-time algorithms $\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$ with message space $\mathcal{M}$, key space $\mathcal{K}$ and ciphertext space $\mathcal{C}$ such that:

  1. The key-generation algorithm $\text{Gen}$ takes as input the security parameter $1^n$ and outputs a key $k \in \mathcal{K}$;
  2. The encryption algorithm $\text{Enc}$ takes as input a key $k$ and a plaintext message $m\in \mathcal{M}$, and outputs a ciphertext $c \in \mathcal{C}$.
  3. The decryption algorithm $\text{Dec}$ takes as input a key $k$ and a ciphertext $c \in \mathcal{C}$, and outputs a message $m \in \mathcal{M}$. We denote a generic error by the symbol $\bot$.

It is required that for every $n$, every key $k$ output by $\text{Gen}(1^n)$, and every $m\in \mathcal{M} \subseteq \{0,1\}^*$, it holds that $\text{Dec}_k(\text{Enc}_k(m))=m$, where $\{0,1\}^*$ is the set of all (finite-length) binary strings.

Note that for some practical encryption schemes, sometimes $\mathcal{M}$ depends on the security parameter $n$ (e.g. $\mathcal{M}(n) = \{ 0,1 \}^n$).

Actually, we do not know how to use an encryption scheme for many times clearly if we only know about this definition. There are at least 2 kinds of possible ways to use an encryption scheme:

Type-1. The key is only used one time. It is trivial if $|\mathcal{K}| \geq |\mathcal{M}|$, and it is inconvenient to share the key every time.

Type-2. Several messages are encrypted by using the same key. And there is no need to let $|\mathcal{K}| < |\mathcal{M}|$.

Obviously, the original OTP is type-1. Most modern encryption schemes are type-2. And the notion of IND-EAV in the book is defined for the type-1 schemes.

Let the adversary $A = (A_{1}, A_{2})$, and $\text{atk} \in \{ \text{eav}, \text{cpa}, \text{cca1}, \text{cca2} \}$. The adversarial indistinguishability experiment $\text{PrivK}^{\text{ind1-atk}}_{A, \Pi}(n)$ for a type-1 encryption scheme $\Pi$:

  1. $A_{1}^{O_{1}}$ is given input $1^n$ , and outputs a pair of messages $m_0 , m_1$ with $|m_0| = |m_1|$.

  2. A key $k$ is generated by running $\text{Gen}(1^n )$, and a uniform bit $b \in \{ 0,1\}$ is chosen. Ciphertext $c \leftarrow \text{Enc}_k (m_b )$ is computed and given to $A_{2}^{O_{2}}$. We refer to $c$ as the challenge ciphertext.

  3. $A_{2}^{O_{2}}$ outputs a bit $d$.
  4. The output of the experiment is defined to be $1$ if $b = d$, and $0$ otherwise. If $\text{PrivK}^{\text{ind1-atk}}_{A,\Pi} (n) = 1$, we say that $A$ succeeds.

If $\text{atk} = \text{eav}$, then $O_{1} = \varepsilon$ and $O_{2} = \varepsilon$.

If $\text{atk} = \text{cpa}$, then $O_{1} = \text{Enc}_{k}(\cdot)$ and $O_{2} = \text{Enc}_{k}(\cdot)$.

If $\text{atk} = \text{cca1}$, then $O_{1} = \text{Enc}_{k}(\cdot)$ and $O_{2} = (\text{Enc}_{k}(\cdot),~\text{Dec}_{k}(\cdot))$.

If $\text{atk} = \text{cca2}$, then $O_{1} = (\text{Enc}_{k}(\cdot),~\text{Dec}_{k}(\cdot))$ and $O_{2} = (\text{Enc}_{k}(\cdot),~\text{Dec}_{k}(\cdot))$.

If we want to consider about the security of the type-2 encryption schemes, the definition above does not work. We need modify it. The problem is how to modify it. Consider it in real world, the adversary $A$ wants to distinguish the challenge ciphertext $c$. $A_{1}$ gets strings from the channel before receiving $c$ and $A_{2}$ gets strings from the channel after receiving $c$. If $\Pi$ is type-2, every time the adversary receives the ciphertext, the key is different.

Let the adversary $A = (A_{1}, A_{2})$, and $\text{atk} \in \{ \text{eav}, \text{cpa}, \text{cca1}, \text{cca2} \}$. The adversarial indistinguishability experiment $\text{PrivK}^{\text{ind2-atk}}_{A, \Pi}(n)$ for a type-2 encryption scheme $\Pi$:

  1. $A_{1}^{O_{1}}$ is given input $1^n$ , and outputs a pair of messages $m_0 , m_1$ with $|m_0| = |m_1|$.

  2. A key $k$ is generated by running $\text{Gen}(1^n )$, and a uniform bit $b \in \{ 0,1\}$ is chosen. Ciphertext $c \leftarrow \text{Enc}_k (m_b )$ is computed and given to $A_{2}^{O_{2}}$.

  3. $A_{2}^{O_{2}}$ outputs a bit $d$.
  4. The output of the experiment is defined to be $1$ if $b = d$, and $0$ otherwise. If $\text{PrivK}^{\text{ind2-eav}}_{A,\Pi} (n) = 1$, we say that $A$ succeeds.

If $\text{atk} = \text{eav}$, then $O_{1} = \varepsilon$ and $O_{2} = \varepsilon$.

If $\text{atk} = \text{cpa}$, then $O_{1} = \text{Enc}_{\text{Gen}(1^n)}(\cdot)$ and $O_{2} = \text{Enc}_{\text{Gen}(1^n)}(\cdot)$.

If $\text{atk} = \text{cca1}$, then $O_{1} = \text{Enc}_{\text{Gen}(1^n)}(\cdot)$ and $O_{2} = (\text{Enc}_{\text{Gen}(1^n)}(\cdot),~\text{Dec}_{\text{Gen}(1^n)}(\cdot))$.

If $\text{atk} = \text{cca2}$, then $O_{1} = (\text{Enc}_{\text{Gen}(1^n)}(\cdot),~\text{Dec}_{\text{Gen}(1^n)}(\cdot))$ and $O_{2} = (\text{Enc}_{\text{Gen}(1^n)}(\cdot),~\text{Dec}_{\text{Gen}(1^n)}(\cdot))$.

What is the relation among the different indistinguishability of type-2 encryption schemes? It is easy to see that IND2-EAV, IND2-CPA, IND2-CCA1, IND2-CCA2 are equivalence. $$\text{IND2-EAV} \Leftrightarrow \text{IND2-CPA} \Leftrightarrow \text{IND2-CCA1} \Leftrightarrow \text{IND2-CCA2}$$

What is the relation between the indistinguishability of two types of encryption schemes? It is also easy to see that $$\text{IND1-EAV} \Leftrightarrow \text{IND2-EAV}$$

Hence, we just need to consider the $\text{PrivK}_{A, \Pi}^{\text{ind1-eav}}(\cdot)$ if we regard $\Pi$ as a type-2 encryption scheme. In other words, there is no reason to consider CPA or CCA of a type-2 encryption scheme, since IND2-EVA is strong enough.

Now, we can talk about the security of some classical encryption schemes.

As we know, type-2 OTP is perfectly security. $\text{PrivK}_{A, \text{OTP}}^{\text{ind2-eav}}(n) = 1/2$ always holds true even $A$ has infinite power, since

$$\Pr[M = m \mid C = c] = \Pr [M = m]$$

And PRG+OTP is secure in the sense of IND2-ATK (also IND1-EAV). It is obvious that OTP and PRG+OTP are both insecure in the sense of IND1-CPA (we must regard them as the type-1 encryption schemes if we are talking about IND1-CPA).

$\endgroup$
  • 1
    $\begingroup$ This answer doesn't address security—it just reflects a limitation in Katz & Lindell's definitions, which may serve a pedagogical purpose but don't reflect practice in the literature. The two most widely used ciphers today, AES-GCM and ChaCha/Poly1305 in TLS 1.3, which keep a message sequence number as state, also technically fail to conform to this definition. If you simply add state into the model, then the encryption oracle can simply remember the number of messages for AES-GCM and ChaCha/Poly1305, or how much of the pad has been peeled off for OTP, and you get IND-CPA security. $\endgroup$ – Squeamish Ossifrage Aug 21 at 15:57
0
$\begingroup$

IMO, CPA on OTP will allow an opponent to study how the key is built.

For example, it could reveal that the key is weak because the RNG is crypto weak or well known, or that the seed is weak. (or worse, that the key is short, repeated, or a function of itself etc).

You end up attacking the key generator.

(the key could be long, non repeating, used only once, but still be generated from a weak source - weak generator, or weak seed set)

$\endgroup$
  • 2
    $\begingroup$ OTP assumes a perfectly random key. OTP is a largely theoretical construction as it is almost impossible to proof that. In the end your answer then becomes: an adversary can use CPA to show that construction isn't a strict OTP. This seems to be a largely theoretical question however - for a practical situation your answer would be more applicable. Oh, almost forgot, welcome to crypto! $\endgroup$ – Maarten Bodewes Aug 30 '18 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.