Security game oracle queries

Question

Concerning private key (symmetric) IND-CPA game definition:

1. Attacker $A$ queries the encryption oracle polynomial number of times.
2. $A$ sends the challenger $C$ a message pair $m_0$ and $m_1$. $C$ picks a random bit $b$ and sends back to $A$ a cyphertext $Enc(m_b)$.
3. $A$ makes further queries to the encryption oracle polynomial number of times.
4. $A$ tries to guess $b$.

An encryption system is considered broken if $A$ has a non-negligible advantage in guessing $b$.

My question is:

1. Let's denote the original game as $Game_0$. Now we remove step (3), i.e. $A$ cannot query the oracle after receiving the challenge cyphertext. We call this $Game_1$. Is it true that if $A$ can break $Game_0$, she can necessarily break $Game_1$? In other words, does any encryption system exist such that $A$ cannot break $Game_1$, but can break $Game_0$ with the extra queries after receiving the cyphertext?

2. Similarly, now we remove step (1), i.e. $A$ cannot query the oracle before receiving the challenge cyphertext. We call this $Game_2$. Is it true that if $A$ can break $Game_0$, she can necessarily break $Game_2$? In other words, does any encryption system exist such that $A$ cannot break $Game_2$, but can break $Game_0$ with the extra queries before receiving the cyphertext?

Answer 1

I will think more about a proof/counterexample for #1, but here is a counterexample for #2.

Let $\mathsf{KeyGen},\mathsf{Enc},\mathsf{Dec}$ refer to a CPA-secure encryption scheme with message space $\{0,1\}^\lambda$, and define the following modified scheme:

• $\mathsf{KeyGen}'$: run $sk \gets \mathsf{KeyGen}$ and sample $m^* \gets \{0,1\}^\lambda$. The key is $(sk,m^*)$.
• $\mathsf{Enc}'( (sk,m^*),m)$: if $m = m^*$ then output $\star$; otherwise output $(\mathsf{Enc}(sk,m), m^*)$.
• $\mathsf{Dec}'( (sk,m^*), c)$: if $c = \star$ then output $m^*$; otherwise parse $c$ as $(c_1,c_2)$ and output $\mathsf{Dec}(sk, c_1)$

The idea is that $m^*$ is a special message whose encryptions are easily distinguishable. But the only way to learn $m^*$ is to query the encryption oracle.

Suppose you play the CPA game with pre-challenge queries. Make any query and the response will include $m^*$. Now choose as your challenge $m_0 = m^* \ne m_1$. You can determine $b$ exactly by seeing whether the challenge ciphertext is $\star$.

Suppose you play the CPA game without pre-challenge queries. With no information about the "magic" plaintext $m^*$ you will not be able to make $m^*$ one of the challenge plaintexts except with negligible probability. So the challenge ciphertext is a regular $\mathsf{Enc}$-encryption of $m_b$ and the game can be reduced to the CPA game for $\mathsf{Enc}$.

---

Update: For #1 the best counterexample I can do is a stateful encryption scheme. It's a bit of a cheat but one could argue that the "right" definition of security for stateless encryption should also be the "right" definition for stateful encryption.

Let $\textsf{Enc}$ refer to a standard CPA-secure encryption, and define the following encryption scheme with internal state $st$, initialized to $\bot$:

• $\textsf{Enc}'(sk,m)$: output $(\textsf{Enc}(sk,m), st)$; update $st = m$.

Every time you encrypt, you are also told the plaintext that was used in the previous ciphertext! So breaking CPA with post-challenge queries is trivial. But with no post-challenge queries, things reduce to the CPA security of $\textsf{Enc}$ in a straight-forward way (the reduction already "knows" the plaintexts used for pre-challenge queries, so can add them on appropriately).

Answer 2

The Game described in #1 is equivalent to IND-CPA security according the CRYPTUTOR wiki from UIUC (The section on modifications). This may explain why Mikero had trouble coming up with a counter example.