Is non-adaptive CPA strictly weaker than standard CPA security?

Question

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.

Answer 1

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.

Answer 2

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.