Примечание: здесь я использую индексы $0,1,2$ и $0,1$ вместо $1, 2, 3$ и $1,2$.
Мы должны показать $3$-проблема неразличимости эквивалентна $2$- неразличимость одна.
$2$- неразличимость легче, чем $3$-неразличимость.
Сначала давайте рассмотрим, что существует противник $\mathcal{A}_3$ против
$3$-проблема неразличимости с преимуществом $\эпсилон$.
Определять $\mathcal{B}^{\mathcal{A}_3}_2$:
Получить три сообщения $(м_0, м_1, м_2)$ от $\mathcal{A}_3$
$x \xleftarrow{\$} \mathbb{Z}_3$
$(m^\prime_0, m^\prime_1) := (m_{(1+ x \mod 3)}, m_{(2+ x \mod 3)})$
послать $(м^\prime_0, м^\prime_1)$ претенденту и получить $с$.
послать $с$ к $\mathcal{A}_3$ и получить $b$.
Если $б=х$ затем вернуть случайный бит $b^\prime$ иначе вернуться $(b-x\mod 3)$.
Сначала докажем, что $\mathcal{B}_2$ имеет вероятность выиграть $\frac{1-\epsilon}{4} +\epsilon$.
Пусть звонит $b''$ бит, выбранный претендентом.
$\mathbb{P}(\mathcal{B}_2 победы)= \mathbb{P}(b- x \mod 3 = b'')\mathbb{P}(\mathcal{B}_2 победы|
б- х \mod 3 = б'') +
\mathbb{P}(b- x \mod 3 \neq b'')\mathbb{P}(\mathcal{B}_2 выигрывает|
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$
Теперь мы можем посмотреть преимущество:
$|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|=|\frac{1- 3 \epsilon}{4}| = \frac{1}{12}|\frac{1}{3}- \epsilon|$.
Если $|\frac{1}{3}- \epsilon|$ не пренебрежимо мало, это подразумевает $|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|$ также не является незначительным.
$3$- неразличимость легче, чем $2$-неразличимость.
Теперь давайте рассмотрим, что существует противник $\mathcal{A}_2$ против
$2$-проблема неразличимости с преимуществом $\эпсилон$.
Определять $\mathcal{B}^{\mathcal{A}_2}_3$:
Получить два сообщения $(м_0, м_1)$от $\mathcal{A}_2$
$b \xleftarrow{\$} \mathbb{Z}_2$
$m_2 := m_{b}$
послать $(м_0, м_1, м_2)$ претенденту и получить $с$.
послать $с$ к $\mathcal{A}_2$ и получить $b^\prime$.
$x \xleftarrow{\$} \big\{b, 2\big\}$
Если $b^\prime=b$ затем верните x, иначе верните $b^\prime$
При первом доказательстве вычислите вероятность выигрыша для $\mathcal{B}_3$.
$\mathbb{P}(\mathcal{B}_3 победы) =
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 победы|b''=2) +
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 победы| b''=b)+
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 победы| b''=1 - b) $
$\mathbb{P}(\mathcal{B}_3 победы) =
\frac{1}{3}\mathbb{P}(b'=b \клин x=2|b''=2) +
\frac{1}{3}\mathbb{P}(b'=b \клин x=b| b''=b)+
\ гидроразрыва {\ эпсилон} {3}. $
Так как $х$ выбирается независимо от $b'$:
$\mathbb{P}(\mathcal{B}_3 победы)$
$= \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')+
\фракция{\эпсилон}{3} $
$\mathbb{P}(\mathcal{B}_3 победы) =
\frac{1}{3}\epsilon \cdot \frac1 2 +
\frac{1}{3}\epsilon \cdot \frac1 2+
\ гидроразрыва {\ эпсилон} {3} = \ гидроразрыва {2 \ эпсилон} {3}. $
Теперь вычисляем преимущество $\mathcal{B}_3$:
$|\frac1 3 - \frac{2\epsilon}{3} |= \frac1 6 |\frac 1 2 - \epsilon|.$
Если $|\frac{1}{2}- \epsilon|$ не пренебрежимо мало, это подразумевает $|\frac{1}{3} - \frac{2\epsilon}{3}|$ также не является незначительным.
Мы делаем вывод, что эти проблемы эквивалентны.
