Content and Informal Problem

Suppose a protocol $\pi$ doing an arbitrary task between two users A and B. I only know that $\pi$ relies on a IND-CPA symmetric encryption scheme $\mathcal{E} = $(KeyGen, Enc, Dec). In details, A holds a key $k$ in $\pi$ computes encryptions of $n$ messages $m_1, \dots, m_n$, providing to B the ciphertexts $\psi_1, \dots, \psi_n$.

To prove the security of $\pi$, I compute a sequence of games, where intuitively I replace a message $m_i$ by a random value $r_i$. Hence, if an adversary $\mathcal{A}$ is able to distinguish if the ciphertext $\psi_i$ contains either $m_i$ or $r_i$ with non-negligible probability, then I can construct an adversary $\mathcal{B}$ able to win at the IND-CPA game with a non-negligible probability as well.

My question is: how to compute the advantage of $\mathcal{B}$ for the IND-CPA game ?

The notation

Before to explain my attempt, I give my notations.

Let $\pi_0$ be the protocol $\pi$ where $\psi_i$ contains $m_i$, and $\pi_1$ the protocol $\pi$ where $\psi_i$ contains $r_i$. I denote the distinguisher able to distinguish between $\pi_0$ and $\pi_1$ by $\mathcal{A}$ the distinguisher. Its advantage to distuinguish is denoted by

$$\mathsf{Adv}^{\pi_0, \pi_1}_{\mathcal{A}} = |\mathsf{Pr}[\mathsf{Exp}^{\pi_0}(\mathcal{A}) \rightarrow 1] - \mathsf{Pr}[\mathsf{Exp}^{\pi_1}(\mathcal{A}) \rightarrow 1]|$$

My Attempt

First, I assumed by contradiction that $\mathsf{Adv}^{\pi_0, \pi_1}_{\mathcal{A}} = \epsilon$ is non-negligible.

I construct my adversary $\mathcal{B}$ playing against the IND-CPA game, which has access to the encryption oracle $Enc(k, \cdot)$ where $k$ is the secret key hold by the IND-CPA challenger. \textsf{B} works as follow:

  1. $\mathcal{B}$ calls the encryption oracle to obtain the necessary encryptions to simulate properly the protocol $\pi_b$ ($b$ will be defined after by the challenger).
  2. $\mathcal{B}$ sends to the challenger the messages $m_0 = m_i$ and $m_i = r_i$, which responds with $\psi_i$ corresponding to the message $m_b$, where $b$ is chosen at random.
  3. $\mathcal{B}$ activates $\mathcal{A}$ with the appropriate input in order to simuate $\pi_b$.
  4. $\mathcal{A}$ sends its response bit $b'$ to $\mathcal{B}$ which forward the bit to the challenger.

Here, I want to compute the advantage of $\mathcal{B}$ against the IND-CPA game, namely, $\mathsf{Adv}^{IND-CPA}_{\mathcal{B}} = |\mathsf{Pr}[b = b'] - \frac{1}{2}|$.

The only things I got is to compute $\mathsf{Pr}[b = b']$, that I computed as follow: \begin{align} \mathsf{Pr}[b = b'] \end{align} \begin{align} =& \mathsf{Pr}[b = 0] \cdot \mathsf{Pr}[b' = 0 | b = 0] + \mathsf{Pr}[b = 1] \cdot \mathsf{Pr}[b' = 1 | b = 1] \end{align} \begin{align} =& \frac{1}{2} \cdot \mathsf{Pr}[b' = 0 | b = 0] + \frac{1}{2} \mathsf{Pr}[b' = 1 | b = 1]\\ \end{align} \begin{align} =& \frac{1}{2} \cdot \mathsf{Pr}[b' = 0 | b = 0] + \frac{1}{2} ( 1 - \mathsf{Pr}[b' = 0 | b = 1])\\ \end{align} \begin{align} =& \frac{1}{2} + \frac{1}{2} \cdot ( \mathsf{Pr}[b' = 0 | b = 0] - \mathsf{Pr}[b' = 0 | b = 1])\\ \end{align}

This is where my problem arise: I need to reformulat the advantage of my distinguisher as follow: $$\mathsf{Adv}^{\pi_0, \pi_1}_{\mathcal{A}} = |\mathsf{Pr}[\mathsf{Exp}^{\pi_0}(\mathcal{A}) \rightarrow 1] - \mathsf{Pr}[\mathsf{Exp}^{\pi_1}(\mathcal{A}) \rightarrow 0]|$$

After this reformulation, I can conclude the reduction:

\begin{align} \mathsf{Pr}[b = b'] = \frac{1}{2} + \frac{1}{2} \cdot \mathsf{Adv}^{\pi_0, \pi_1}_{\mathcal{A}} = \frac{1}{2} + \frac{1}{2} + \epsilon\\ \end{align}

leading to the advantage in the IND-CPA of $\mathsf{Adv}^{IND-CPA}_{\mathcal{B}} = \frac{1}{2} \cdot \epsilon$

The problem

Can I compute the reduction without doing the reformulation of the advantage for the distinguisher ?

I hope my problem was clearly stated and explained.

Have a good day !


1 Answer 1


I don't fully understand what you mean by "without doing a reformulation...". For a standard proof of what you want, see for example Theorem 1 of BDJR97.


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.