# Challenge-Response Phases in IND-CPA

The IND-CPA game has two challenge-response phases

1. A key is generated by running $Gen(1^n)$ and challenger selects a bit b {0,1} uniformly at random.

2. Adversary gets input $1^n$.

3. Can query the oracle a polynomial number of times with messages and gets $E_k(m)$ back.

4. Attacker sends messages $m_0$, $m_1$, challenger returns $E_k(m_b)$.

5. Can query the oracle a polynomial number of times with messages and gets $E_k(m)$ back.

Why are these two challenge-response phases (3,5) necessary? I understand why at least one phase is necessary (ex: to ensure that deterministic algorithms are not IND-CPA secure), but why both?

-
Don't forget to select an answer if one of the responses sufficiently answers your question. If not, could you indicate what's missing? – Maarten Bodewes Nov 8 '15 at 17:17

You need to allow queries before the attacker outputs $m_0,m_1$ since maybe the queries help the attacker choose $m_0,m_1$ that are "easier" for it to attack.

You need to allow queries after the attacker receives back the challenge ciphertext $c=E_k(m_b)$ since knowing $c$ may make it possible to generate a plaintext whose encryption helps to know what $c$ is.

-

The oracle in step 3 is absolutely necessary. Check the answer to this question for an example that would break IND-CPA security otherwise.

On the other hand, the oracle in step 5 may be unnecessary for IND-CPA security according to the alternate formulations of IND-CPA suggested in the CRYPTUTOR wiki from UIUC.

-
As the author of that wiki page, I wouldn't take it as definitive. Maybe I had thought about it quite carefully when writing it, but my intuition seeing it today is that you need encryption queries before and after the challenge ciphertext gets generated. – Mikero Nov 9 '15 at 22:03
Do any of you know some proof of either of the options. I've seen people state that step 5 is not necessary, but I have never seen a proof. – hsgubert Dec 13 '15 at 4:53