6
$\begingroup$

Today during a cryptography lecture an interesting question came up: Whether non-adaptive CPA security is equivalent to adaptive (FtG / LOR) CPA security.

Now for a short description of what this CPA1 / non-adaptive definition means:

  • The challenger generates a key $k\gets \operatorname{Gen}(1^n)$
  • The stateful adversary $\mathcal A$ is initially run on $1^n$ with access to $\operatorname{Enc}_k(\cdot)$ and outputs two equal-length messages $(m_0,m_1)$
  • A bit $b$ is chosen uniformly at random and $c_b=\operatorname{Enc}_k(m_b)$ is computed
  • The adversary $\mathcal A$ is resumed / run on $c_b$ and $1^n$ but not given access to $\operatorname{Enc}_k$ and has to output a bit $b'$
  • $\mathcal A$ wins iff $b=b'$

You may recognize this definition to be the standard Find-Then-Guess CPA definition with access to the encryption oracle removed after the challenge messages are output. So the adversary can use the encryption oracle to find the challenge messages but can't use it on any function of the challenge ciphertext.

So:
Is there an encryption scheme that is CPA1 but not CPA secure?

Intuitively it feels like this definition is weaker because encryption queries cannot depend on the challenge ciphertext but I currently see no way to exploit this such that CPA1 security is still preserved.


I know this is true for CCA because we know NM-CCA1 $\implies$ IND-CCA1 and IND-CCA2 $\implies$ NM-CCA2 but NM-CCA1 $\implies$ NM-CCA2 doesn't hold.
I also know that CPA1 security is stronger than eavesdropping security because deterministic schemes can be broken by querying the encryption oracle before the challenge query.

$\endgroup$
2
$\begingroup$

Edit. Except for CPA1 (defined by the OP), "CPA" below refers to multi-challenge CPA, where the adversary always submits two messages and receive the encryption of either the first or the second messages. It's equivalent to the usual one-challenge multi-query CPA.

CPA1 is equivalent to CPA. Consider real-or-random CPA (RRCPA), where the adversary adaptively chooses messages and receive either encryptions of the chosen messages or encryptions of random messages. It is routine to see that CPA is tightly equivalent to RRCPA. Lastly, RRCPA reduces to CPA1 via a standard hybrid argument, as the encryption of random messages can be queried before the challenge. The proof is not tight, though.

In more detail, let $\mathcal{A}$ be an adversary against RRCPA, we construct $\mathcal{B}$ against CPA1. Let $Q$ be a polynomial that upper-bounds the number of challenges $\mathcal{A}$ makes. $\mathcal{B}$ does the following:

  1. Sample $i\gets[Q]$ and launch $\mathcal{A}$.
  2. For the first ${(i-1)}$ challenges $m_1,\dots,m_{i-1}$ that $\mathcal{A}$ makes, query the encryption oracle to obtain the correct ciphertexts $c_1,\dots,c_{i-1}$ and use them as the response to $\mathcal{A}$.
  3. Sample ${Q-(i-1)}$ random messages $m_i',\dots,m_Q'$ and query the encryption oracle to get the ciphertexts $c_{i+1},\dots,c_Q$ (without $c_i$).
  4. When $\mathcal{A}$ makes the $i$th challenge $m_i$, submit $m_i,m_i'$ to the CPA1 challenger and gets back a ciphertext $c_i$. Use it to respond to $\mathcal{A}$.
  5. For the other challenges from $\mathcal{A}$, use $c_{i+1},\dots,c_Q$ as the responses.

Let $H_i$ be the hybrid of RRCPA such that the first $i$ challenges are real and the other are random, and $G_b$ the CPA1 experiments. Clearly, $\mathcal{A}$ is in $H_{i-1+b}$ if $\mathcal{B}$ is in $G_b$ and chooses $i$ at the beginning. Averaging over $i$ shows that the advantage of $\mathcal{B}$ is $1/Q$ that of $\mathcal{A}$. This finishes the reduction.

$\endgroup$
  • $\begingroup$ A note to the interested reader: "multi-challenge CPA" is also known as left-or-right (LOR) CPA and "one-challenge multi-query CPA" is also known as Find-then-Guess (FtG) CPA. $\endgroup$ – SEJPM Mar 2 at 15:03
1
$\begingroup$

I misunderstood the question

You wrote your question in a way that the adversary sees only a single ciphertext. Therefore, OTP satisfies your definition but is not CPA secure. This is probably not what you had in mind. I think you should consider a definition where $\cal A$ outputs $(m_{1,0},m_{1,1}), (m_{2,0},m_{2,1}), \ldots, (m_{n,0},m_{n,1})$ and gets back encryptions of $m_{1,b}, \ldots, m_{n,b}$.

An easy example that separates adaptive from non-adaptive CPA is the following. Start with a good encryption scheme $(K,E,D)$ and define a new one $(K^*,E^*,D^*)$:

  • $K^*$: run $k \gets K$ and also choose random plaintext $m^*$. The key is $(k,m^*)$.
  • $E^*$: given plaintext $m$ and key $(k,m^*)$: if $m \ne m^*$ then just run $c\gets E(k,m)$ and output $(c,m^*)$. Otherwise give output $\bot$.

The scheme has one "bad plaintext" $m^*$ that is chosen randomly. Encryptions of the bad plaintext are easily distinguishable from all other plaintexts. The identity of the bad plaintext is appended to all other ciphertexts. This enables an adaptive attack without undermining the nonadaptive security.

More formally:

This scheme satisfies nonadaptive-CPA security because the choice of bad plaintext $m^*$ is independent of the adversary's choice of challenge plaintexts. With overwhelming probability (assuming an exponentially large space of plaintexts), none of the adversary's challenge plaintexts equals $m^*$ and the security of $E^*$ easily reduces to that of $E$.

The scheme is vulnerable to an adaptive-CPA attack, where the adversary requests the encryption of any plaintext, and learns $m^*$ from the ciphertext. Now it can ask for an encryption of $m^*$ and any other $m' \ne m^*$ and easily tell them apart.

$\endgroup$
  • 1
    $\begingroup$ I think you misread the definition in the question. The adversary has access to an encryption oracle before they output the challenge messages. This means that neither is OTP secure in this definition (query $0^n$ to learn the key beforehand) nor is the scheme you describe. With a single query the adversary trivially learns $m^*$ before choosing the challenge messages. $\endgroup$ – Maeher Nov 27 '19 at 7:14
  • $\begingroup$ @Maeher I think Mikero assumed $\mathcal A$ to be stateless between invocations resulting in this answer whereas you and I assumed $\mathcal A$ to preserve state between having access to the encryption oracle and having to act upon the challenge ciphertext. $\endgroup$ – SEJPM Nov 27 '19 at 13:26
  • $\begingroup$ @SEJPM I don't think so. Even a stateless $\mathcal{A}$ can run the attack against the described scheme. Make an arbitrary query to learn $m^*$, output $m^*$ and $m'\neq m^*$. When you receive the challege ciphertext $c$, having no recollection of the value of $m^*$, just check whether $c=\bot$. $\endgroup$ – Maeher Nov 27 '19 at 16:23
  • 1
    $\begingroup$ Yes, it looks like I misunderstood the question. I'll think about it some more and possibly write a new answer. $\endgroup$ – Mikero Nov 27 '19 at 19:01

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.