Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
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 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.

share|improve this answer

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.

share|improve this answer
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 at 22:03

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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