Observație: aici folosesc indecșii $0,1,2$ și $0,1$ în loc de $1, 2, 3$ și $1,2$.
Trebuie să arătăm $3$-problema de indistingere este echivalentă cu $2$-nedistingere unul.
$2$-indistinguirea este mai usoara decat $3$-indistincbilitatea.
Mai întâi să considerăm că există un adversar $\mathcal{A}_3$ impotriva
$3$-problema de indistinctie cu avantaj $\epsilon$.
Defini $\mathcal{B}^{\mathcal{A}_3}_2$:
Primiți trei mesaje $(m_0, m_1, m_2)$ din $\mathcal{A}_3$
$x \xleftarrow{\$} \mathbb{Z}_3$
$(m^\prime_0, m^\prime_1) := (m_{(1+ x \mod 3)}, m_{(2+ x \mod 3)})$
Trimite $(m^\prime_0, m^\prime_1)$ contestatorului și primiți $c$.
Trimite $c$ la $\mathcal{A}_3$ și primiți $b$.
Dacă $b=x$ apoi returnează un bit aleatoriu $b^\prime$ altfel reveni $(b- x \mod 3)$.
Mai întâi dovedim asta $\mathcal{B}_2$ are probabilitatea de a câștiga $\frac{1-\epsilon}{4} +\epsilon$.
Lasă să sune $b''$ bitul ales de contestator.
$\mathbb{P}(\mathcal{B}_2 victorii)= \mathbb{P}(b- x \mod 3 = b'')\mathbb{P}(\mathcal{B}_2 victorii|
b- x \mod 3 = b'') +
\mathbb{P}(b- x \mod 3 \neq b'')\mathbb{P}(\mathcal{B}_2 victorii|
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$
Acum putem privi avantajul:
$|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|=|\frac{1-3 \epsilon}{4}| = \frac{1}{12}|\frac{1}{3}- \epsilon|$.
Dacă $|\frac{1}{3}- \epsilon|$ este deloc neglijabilă, implică $|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|$ este, de asemenea, deloc neglijabilă.
$3$-indistinguirea este mai usoara decat $2$-indistincbilitatea.
Acum să considerăm că există un adversar $\mathcal{A}_2$ impotriva
$2$-problema de indistinctie cu avantaj $\epsilon$.
Defini $\mathcal{B}^{\mathcal{A}_2}_3$:
Primiți două mesaje $(m_0, m_1)$din $\mathcal{A}_2$
$b \xleftarrow{\$} \mathbb{Z}_2$
$m_2 := m_{b}$
Trimite $(m_0, m_1, m_2)$ contestatorului și primiți $c$.
Trimite $c$ la $\mathcal{A}_2$ și primiți $b^\prime$.
$x \xleftarrow{\$} \big\{b, 2\big\}$
Dacă $b^\prime=b$ apoi returnează x altfel returnează $b^\prime$
Când se dovedește prima dată, calculează probabilitatea de a câștiga pentru $\mathcal{B}_3$.
$\mathbb{P}(\mathcal{B}_3 victorii) =
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 victorii|b''=2) +
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 victorii| b''=b)+
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 victorii| b''=1 - b) $
$\mathbb{P}(\mathcal{B}_3 victorii) =
\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}.$
pentru că $x$ este ales independent de $b'$:
$\mathbb{P}(\mathcal{B}_3 victorii)$
$= \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 victorii) =
\frac{1}{3}\epsilon \cdot \frac1 2 +
\frac{1}{3}\epsilon \cdot \frac1 2+
\frac{\epsilon}{3} = \frac{2\epsilon}{3}.$
Acum calculăm avantajul $\mathcal{B}_3$:
$|\frac1 3 - \frac{2\epsilon}{3} |= \frac1 6 |\frac 1 2 - \epsilon|.$
Dacă $|\frac{1}{2}- \epsilon|$ este deloc neglijabilă, implică $|\frac{1}{3} - \frac{2\epsilon}{3}|$ este, de asemenea, deloc neglijabilă.
Deducem că aceste probleme sunt echivalente.
