6
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Oh wow this is an ingenious design with awesome explanation. Thank you so much Mikero!! I'll direct my effort to solving Game_1 now. $\endgroup$ – Ainz Titor Oct 30 '15 at 5:15
  • $\begingroup$ I think you mean the encryption scheme can't be stateful. It doesn't make sense to have a stateless attacker. $\endgroup$ – Mikero Oct 30 '15 at 15:55
1
$\begingroup$

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.

$\endgroup$

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.