Is non-adaptive CPA strictly weaker than standard CPA security? 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.
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:


Sample $i\gets[Q]$ and launch $\mathcal{A}$.
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}$.
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$).
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}$.
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.