5
$\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$
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.