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:
- $\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).
- $\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.
- $\mathcal{B}$ activates $\mathcal{A}$ with the appropriate input in order to simuate $\pi_b$.
- $\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 !
