# Reduction from Distinguisher to Indishtinguishability

## 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 !