6
$\begingroup$

The CRYPTUTOR wiki from UIUC uses the following definition of the IND-CPA game:

  1. We (privately) choose a key K according to the key generation algorithm: K $\gets \mathsf{KeyGen}$.
  2. We (privately) choose a random bit b $\gets \{0,1\}$.
  3. Repeatedly do:
    • A is allowed (any number of times) to query an oracle that computes the functionality $\mathsf{Enc}_K$.
    • Challenge: A outputs two messages, $m_0\, $and $m_1\,$.
    • Response: We give A the ciphertext $\mathsf{Enc}_K(m_b)$

A outputs $b'\,$ (i.e, a guess for our b).

We say that the advantage of A in this experiment is $\Pr[ b = b' ] - 1/2$.

Later in the Modifications section it is stated as follows:

Using an application of a hybrid argument, it can be shown that only one "challenge-response" phase is necessary. It does not affect the definition of security to remove the repeating loop (line 3).

I am not able to come up with any hybrid arguments to prove this.

$\endgroup$
2
  • $\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. In general, these technical details of security definitions can be quite subtle and unexpected. $\endgroup$
    – Mikero
    Nov 9, 2015 at 22:03
  • $\begingroup$ I see. If they are indeed not equivalent, we should be able to come up with a broken scheme as in this question. And, coming up with a stateless broken scheme seems very difficult too. We should be able to prove it one way or the other, which seems elusive so far. $\endgroup$
    – thegreat2
    Nov 10, 2015 at 0:53

1 Answer 1

1
$\begingroup$

EDIT: I realised that I assumed an IND-CPA game where the adversary has pre- and post-challenge access to the encryption oracle and not only pre-challenge access. I'll edit my answer soon.

I'll give the idea and leave the concrete analysis to you. You want to show that single-query IND-CPA implies multi-query IND-CPA or in other words if there is an adversary against multi-query IND-CPA, then there is also one against single-query IND-CPA.

Assume that you have an adversary $\cal A$ that that wins the multi-query IND-CPA experiment with $q$ challenge queries.

For our argumentation below, we construct an adversary $\cal B$ that uses only one challenge query where $\cal B$ interacts with an single-query IND-CPA challenger $\cal C$ of a symmetric encryption scheme.

The idea is that $\cal B$ chooses an index $i\in [q]$ and proceeds as follows:

Let $\cal B$ initialize the single-query IND-CPA game with a challenger $\cal C$ and:

  • For all challenge query $(m_0^j,m_1^j)$ with $j<i$ from $\cal A$, $\cal B$ calls the encryption oralce of $\cal C$ with $m_0^j$ and returns the obtained ciphertext to $\cal A$
  • For the challenge query $(m_0^j,m_1^j)$ with $j=i$, $\cal B$ queries $(m_0^j,m_1^j)$ to the challenge oracle of $\cal C$ and returns whatever $\cal C$ returns
  • For any challenge query $(m_0^j,m_1^j)$ with $j>i$ from $\cal A$, $\cal B$ calls the encryption oralce of $\cal C$ with $m_1^j$ and returns the obtained ciphertext to $\cal A$

If $\cal A$ outputs its guess $b'$ to $\cal B$, then $\cal B$ forwards $b'$ to $\cal C$

Now, define the $j$'th hybrid $H_j$ to be the version of the multi-query IND-CPA game where the first $j$'th queries are with respect to $m_0^j$ (and all remaining with respect to $m_1^j$). It is clear that in $H_0$ all queries are with respect to $m_1$ and in $H_q$ all queries are with respect to $m_0$. Consequently, a distinguisher between these two extreme hybrids $H_0$ and $H_q$ clearly yields a mutli-query IND-CPA adversary.

If we now assume that there is such an multi-query IND-CPA adversary $\cal A'$ that has non-negligible advantage, then if we move from $H_0$ to $H_q$, there must be an $i, 0\leq i < q$ such that for the neighboring hybrids $H_i$ and $H_{i+1}$ it must hold that their distance must be non-negligible (as the number of queries $q$ is polynomially bounded). Now, you can argue that any distinguisher between two neighboring hybrids yields a distinguisher for the single-query IND-CPA game, by exactly using the adversary $\cal B$ defined above. Finally, you will get that the advantage for an adversary of winning the multi-query IND-CPA experiment is less or equal then $q$ times the advantage of an adversary winning the single-query IND-CPA experiment, i.e., any multi-query adversary with non-negligible advantage yields a single-query adversary with non-negligible advantage (which proves what you want to show).

$\endgroup$
2
  • $\begingroup$ About the third point in the description of what B does: For any challenge query $(m_0^j,m_1^j)$ with $j>i$ from $\cal A$, $\cal B$ calls the encryption oralce of $\cal C$ with $m_1^j$ and returns the obtained ciphertext to $\cal A$ This is not possible with the challenger $\cal C$ in the single query game because - according to the definition of the game in question, when the loop is removed, $\cal B$ doesn't have access to $\cal C$'s encryption oracle any more. $\endgroup$
    – thegreat2
    Nov 8, 2015 at 18:40
  • $\begingroup$ Let us continue this discussion in chat. $\endgroup$
    – thegreat2
    Nov 8, 2015 at 20:13

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.