Adversarial Indistinguishability with more messages

Question

Suppose that we play the game from Adversarial Indistinguishability but adversarial can choose three messages $m_0, m_1, m_2$. Of course, $Pr[M=m_i]=1/3$ for $i=0,1,2$. I suppose that to have adversarial indistinguishability, one cannot have an advantage greater than $1/3$. The question is if this is stronger than the version with two messages. Intuitively it is, but then we could take more and more messages and make the advantage of adversarial lesser and lesser. Is it neccessary? For some reason, in the definition, there are two messages - is this enough?

Answer 1

Remark: here I'm using the indexes $0,1,2$ and $0,1$ instead of $1, 2, 3$ and $1,2$.

We have to show the $3$-indistinguishability problem is equivalent to the $2$-indistinguishability one.

$2$-indistinguishability is easier than $3$-indistinguishability.

First let consider it exists an adversary $\mathcal{A}_3$ against the $3$-indistinguishability problem with advantage $\epsilon$.

Define $\mathcal{B}^{\mathcal{A}_3}_2$:

• Receive three messages $(m_0, m_1, m_2)$ from $\mathcal{A}_3$

• $x \xleftarrow{\\\$} \mathbb{Z}_3$

• $(m^\prime_0, m^\prime_1) := (m_{(1+ x \mod 3)}, m_{(2+ x \mod 3)})$

• Send $(m^\prime_0, m^\prime_1)$ to the challenger, and receive $c$.

• Send $c$ to $\mathcal{A}_3$ and receive $b$.

• If $b=x$ then return a random bit $b^\prime$ else return $(b- x \mod 3)$.

We first prove that $\mathcal{B}_2$ has probability to win $\frac{1-\epsilon}{4} +\epsilon$.

Let call $b''$ the bit chosen by the challenger.

$\mathbb{P}(\mathcal{B}_2 wins)= \mathbb{P}(b- x \mod 3 = b'')\mathbb{P}(\mathcal{B}_2 wins| b- x \mod 3 = b'') + \mathbb{P}(b- x \mod 3 \neq b'')\mathbb{P}(\mathcal{B}_2 wins| b- x \mod 3 \neq b'')$

$= \epsilon \cdot 1 + (1 - \epsilon)\mathbb{P}((b=x) \wedge b^\prime =b'' | b- x \mod 3 \neq b^{\prime\prime}) $

$= \epsilon + (1 - \epsilon)\frac{1}{2}\cdot\frac{1}{2}.qed$

Now we can look the advantage: $|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|=|\frac{1- 3 \epsilon}{4}| = \frac{1}{12}|\frac{1}{3}- \epsilon|$.

If $|\frac{1}{3}- \epsilon|$ is non negligible, it implies $|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|$ is also non negligible.

$3$-indistinguishability is easier than $2$-indistinguishability.

Now let consider it exists an adversary $\mathcal{A}_2$ against the $2$-indistinguishability problem with advantage $\epsilon$.

Define $\mathcal{B}^{\mathcal{A}_2}_3$:

• Receive two messages $(m_0, m_1)$ from $\mathcal{A}_2$

• $b \xleftarrow{\\\$} \mathbb{Z}_2$

• $m_2 := m_{b}$

• Send $(m_0, m_1, m_2)$ to the challenger, and receive $c$.

• Send $c$ to $\mathcal{A}_2$ and receive $b^\prime$.

• $x \xleftarrow{\\\$} \big\{b, 2\big\}$

• If $b^\prime=b$ then return $x$ else return $b^\prime$

We first compute the probability to win for $\mathcal{B}_3$.

$\mathbb{P}(\mathcal{B}_3 wins) = \frac{1}{3}\mathbb{P}(\mathcal{B}_3 wins|b''=2) + \frac{1}{3}\mathbb{P}(\mathcal{B}_3 wins| b''=b)+ \frac{1}{3}\mathbb{P}(\mathcal{B}_3 wins| b''=1 - b) $

$\mathbb{P}(\mathcal{B}_3 wins) = \frac{1}{3}\mathbb{P}(b'=b \wedge x=2|b''=2) + \frac{1}{3}\mathbb{P}(b'=b \wedge x=b| b''=b)+ \frac{\epsilon}{3}.$

Because $x$ is picked independently of $b'$:

$\mathbb{P}(\mathcal{B}_3 wins)$ $= \frac{1}{3}\mathbb{P}(b'=b|b''=2) \cdot \mathbb{P}(x=2|b''=2) + \frac{1}{3}\mathbb{P}(b'=b|b''=b') \cdot \mathbb{P}(x=b''|b''=b')+ \frac{\epsilon}{3} $

$\mathbb{P}(\mathcal{B}_3 wins) = \frac{1}{3}\epsilon \cdot \frac1 2 + \frac{1}{3}\epsilon \cdot \frac1 2+ \frac{\epsilon}{3} = \frac{2\epsilon}{3}.$

Now we compute the advantage of $\mathcal{B}_3$: $|\frac1 3 - \frac{2\epsilon}{3} |= \frac1 6 |\frac 1 2 - \epsilon|.$

If $|\frac{1}{2}- \epsilon|$ is non negligible, it implies $|\frac{1}{3} - \frac{2\epsilon}{3}|$ is also non negligible.

We deduce these problems are equivalent.