Tôi hiện đang đọc cái này Cách mô phỏng nó Hướng dẫn về kỹ thuật chứng minh mô phỏng.
Trên P. 10, có một bằng chứng sử dụng mô phỏng cho 1/2-OT, chống lại các đối thủ nửa trung thực. Tóm lại, người chơi $P_1$ giữ tin nhắn $b_0$, $b_1$ và người chơi $P_2$ giữ bit lựa chọn $Ï$. Từ $P_1$ không có đầu ra, nó sẽ tạo một trình giả lập (tr.11 dưới cùng - tr.12 giữa) mô phỏng $P_1$quan điểm của. Vì $P_2$ nó tạo lại một trình giả lập (xem trang 12 dưới cùng - trang 14 ở giữa) nhưng trong khi mô phỏng chế độ xem, nó không thể xuất chính xác $B(α,x_{1-Ï}) \oplus b_{1-Ï}$ vì vậy nó chỉ xuất ra B(α,x_{1-Ï}). Sau đó, nó chứng minh rằng các phân phối của hai thuật ngữ cuối cùng là không thể phân biệt bằng tính toán. Nó giả định rằng có một sự phân biệt $D$ (xem trang 13 giữa - trang 14 giữa) và điều đó đã cho $D$ một thuật toán hiệu quả $A$ có thể được tạo để có thể phá vỡ hình ảnh trước của $B$ (là một vị từ khó tính) với xác suất không đáng kể.
Câu hỏi :
Dựa vào các định nghĩa sau.
Trên trang 13, nó mô tả bộ phân biệt giả định đó $D$ như sau :
Giả sử mâu thuẫn rằng tồn tại một sự không thống nhất
phân biệt thời gian đa thức xác suất $D$, một đa thức $p(·)$ và một loạt các bộ dữ liệu vô hạn $(Ï, b_Ï, n)$ như vậy mà $$Pr[D(Ï, r_0, r_1; α,(B(α,
x_Ï) \oplus b_Ï, B(α, x_{1âÏ}))) = 1] â Pr[D(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α,
x_{1âÏ}) \oplus 1)) = 1] ⥠\dfrac{1}{p(n)}$$ .
Trên P. 13 giữa nó mô tả thuật toán $\mathcal{A}$ :
thuật toán $\mathcal{A}$ được đưa ra $Ï$, $b_Ï$ trên băng tư vấn của nó, và nhận được $(1^n, α, r)$ cho đầu vào. $\mathcal{A}$âs mục đích là để đoán $B(α, f^{â1}_{α}(S(α; r))$. Để làm điều này, mặc nhiên và không biết giá trị thực của nó, $\mathcal{A}$ bộ $x_{1âÏ} = f^{â1}_{α} (S(α; r))$ bằng cách thiết lập $r_{1âÏ} = r$ (từ đầu vào của nó).Tiếp theo, thuật toán $\mathcal{A}$ chọn ngẫu nhiên $r_Ï$, và tính toán $x_Ï = S(α; r_Ï)$ và $β_Ï = B(α, x_Ï) \oplus b_Ï$. Cuối cùng, $\mathcal{A}$ chọn ngẫu nhiên $β_{1âÏ}$, gọi $D$ trên đầu vào $(Ï, r_0, r_1; α,(β_Ï, β_{1âÏ}))$ và đầu ra $β_{1âÏ}$ nếu $D$ đầu ra 1, và $1âβ_1âÏ$ nếu không thì. Quan sát rằng nếu $\mathcal{A}$ phỏng đoán $β_{1âÏ}$ một cách chính xác sau đó nó gọi $D$ trên $(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α, x_{1âÏ})))$, và nếu không thì nó gọi $D$ trên $(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α, x_{1âÏ}) \oplus 1))$. Như vậy, nếu
D xuất 1, sau đó $\mathcal{A}$ cho rằng nó đã đoán $β_{1âÏ}$ đúng (vì $D$
đầu ra 1 với xác suất cao hơn khi được đưa ra $B(α, x_{1âÏ})$ hơn khi cho $B(α, x_{1âÏ}) \oplus 1)$.
Tại sao trong khi $\mathcal{A}$ chọn một ngẫu nhiên $β_{1-Ï}$, khi nó đoán sai nó giống như $D$ được gọi với $(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α, x_{1âÏ}) \oplus 1))$? Tại sao lại là $B(α, x_{1âÏ}) \oplus 1)$ tương đương với ngẫu nhiên $β_{1-Ï}$?
