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?

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

2 Answers 2


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.

  • $\begingroup$ 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. $\endgroup$
    – Mikero
    Nov 9, 2015 at 22:03
  • $\begingroup$ 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. $\endgroup$
    – hsgubert
    Dec 13, 2015 at 4:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.