4
$\begingroup$

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?

Improve this question
$\endgroup$
1
  • $\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 ♦
    Commented Nov 8, 2015 at 17:17

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented 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
    Commented Dec 13, 2015 at 4:53
  • $\begingroup$ @thegreat2 As Yehuda Lindell have answered, "knowing $c$ may make it possible to generate a plaintext whose encryption helps to know what $c$ is." So for security definition to include all the case (not special cases), the oracle in step 5 is indeed necessary. $\endgroup$
    – user1035648
    Commented Feb 3 at 22:19

Your Answer

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

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