Ghi chú: ở đây tôi đang sử dụng các chỉ mục $0,1,2$ và $0,1$ thay vì $1, 2, 3$ và $1,2$.
Chúng ta phải thể hiện $3$- vấn đề không thể phân biệt được tương đương với $2$-không thể phân biệt một.
$2$-không thể phân biệt được dễ dàng hơn so với $3$-không thể phân biệt được.
Đầu tiên hãy coi nó tồn tại một kẻ thù $\mathcal{A}_3$ chống lại
$3$- vấn đề không thể phân biệt với lợi thế $\epsilon$.
Định nghĩa $\mathcal{B}^{\mathcal{A}_3}_2$:
Nhận được ba tin nhắn $(m_0, m_1, m_2)$ từ $\mathcal{A}_3$
$x \xleftarrow{\$} \mathbb{Z}_3$
$(m^\prime_0, m^\prime_1) := (m_{(1+ x \mod 3)}, m_{(2+ x \mod 3)})$
Gửi $(m^\prime_0, m^\prime_1)$ cho người thách thức, và nhận $c$.
Gửi $c$ đến $\mathcal{A}_3$ Và nhận $b$.
Nếu $b=x$ sau đó trả lại một bit ngẫu nhiên $b^\số nguyên tố$ khác trở lại $(b- x \mod 3)$.
Đầu tiên chúng tôi chứng minh rằng $\mathcal{B}_2$ có xác suất thắng $\frac{1-\epsilon}{4} +\epsilon$.
hãy gọi $b''$ bit được chọn bởi người thách đấu.
$\mathbb{P}(\mathcal{B}_2 win)= \mathbb{P}(b- x \mod 3 = b'')\mathbb{P}(\mathcal{B}_2 win|
b- x \mod 3 = b'') +
\mathbb{P}(b- x \mod 3 \neq b'')\mathbb{P}(\mathcal{B}_2 thắng|
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$
Bây giờ chúng ta có thể nhìn vào lợi thế:
$|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|=|\frac{1- 3 \epsilon}{4}| = \frac{1}{12}|\frac{1}{3}- \epsilon|$.
Nếu $|\frac{1}{3}- \epsilon|$ là không đáng kể, nó ngụ ý $|\frac{1}{2} - (\frac{1-\epsilon}{4} +\epsilon)|$ cũng không đáng kể.
$3$-không thể phân biệt được dễ dàng hơn so với $2$-không thể phân biệt được.
Bây giờ hãy coi nó tồn tại một kẻ thù $\mathcal{A}_2$ chống lại
$2$- vấn đề không thể phân biệt với lợi thế $\epsilon$.
Định nghĩa $\mathcal{B}^{\mathcal{A}_2}_3$:
Nhận được hai tin nhắn $(m_0, m_1)$từ $\mathcal{A}_2$
$b \xleftarrow{\$} \mathbb{Z}_2$
$m_2 := m_{b}$
Gửi $(m_0, m_1, m_2)$ cho người thách thức, và nhận $c$.
Gửi $c$ đến $\mathcal{A}_2$ Và nhận $b^\số nguyên tố$.
$x \xleftarrow{\$} \big\{b, 2\big\}$
Nếu $b^\prime=b$ sau đó trở lại x khác trở lại $b^\số nguyên tố$
Người đầu tiên chứng minh tính xác suất để giành chiến thắng cho $\mathcal{B}_3$.
$\mathbb{P}(\mathcal{B}_3 thắng) =
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 thắng|b''=2) +
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 thắng| b''=b)+
\frac{1}{3}\mathbb{P}(\mathcal{B}_3 thắng| b''=1 - b) $
$\mathbb{P}(\mathcal{B}_3 thắng) =
\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}.$
Bởi vì $x$ được chọn độc lập với $b'$:
$\mathbb{P}(\mathcal{B}_3 thắng)$
$= \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 thắng) =
\frac{1}{3}\epsilon \cdot \frac1 2 +
\frac{1}{3}\epsilon \cdot \frac1 2+
\frac{\epsilon}{3} = \frac{2\epsilon}{3}.$
Bây giờ chúng ta tính lợi thế của $\mathcal{B}_3$:
$|\frac1 3 - \frac{2\epsilon}{3} |= \frac1 6 |\frac 1 2 - \epsilon|.$
Nếu $|\frac{1}{2}- \epsilon|$ là không đáng kể, nó ngụ ý $|\frac{1}{3} - \frac{2\epsilon}{3}|$ cũng không đáng kể.
Ta suy ra các bài toán này là tương đương.
