Momentan citesc asta Cum să o simulați â Un tutorial despre tehnica de demonstrare a simulării.
Pe p. 10, există o dovadă folosind simularea pentru 1/2-OT, împotriva adversarilor semi-cinstiți. Pe scurt, jucătorul $P_1$ reține mesajele $b_0$, $b_1$ și jucătorul $P_2$ ține bitul de alegere $Ï$. De cand $P_1$ nu are ieșire, creează un simulator (p.11 jos - p.12 mijloc) care simulează $P_1$punctul de vedere al lui. Pentru $P_2$ creează din nou un simulator (vezi p.12 jos - p.14 mijloc), dar în timp ce simulează vizualizarea nu poate scoate exact $B(α,x_{1-Ï}) \oplus b_{1-Ï}$ deci iese doar B(α,x_{1-Ï}). Apoi demonstrează că distribuțiile ultimilor doi termeni nu se pot distinge din punct de vedere computațional. Se presupune că există un deosebitor $D$ (vezi p. 13 mijloc - p. 14 mijloc) și că dat $D$ un algoritm eficient $A$ pot fi create care pot rupe găsi pre-imagine a $B$ (care este un predicat hardcore) cu probabilitate neglijabilă.
intrebare:
Pe baza următoarelor definiții.
La p.13 descrie acel presupus deosebitor $D$ după cum urmează :
Presupunem prin contradicție că există o neuniformă
distinctor de timp polinomial probabilistic $D$, un polinom $p(·)$ și o serie infinită de tupluri $(Ï, b_Ï, n)$ astfel încât $$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)}$$ .
Pe p. 13 mijloc descrie algoritmul $\mathcal{A}$ :
Algoritm $\mathcal{A}$ este dată $Ï$, $b_Ï$ pe banda sa de sfaturi, și primește $(1^n, α, r)$ pentru intrare. $\mathcal{A}$Scopul este de a ghici $B(α, f^{â1}_{α}(S(α; r))$. Pentru a face acest lucru, implicit și fără a-i cunoaște valoarea reală, $\mathcal{A}$ seturi $x_{1âÏ} = f^{â1}_{α} (S(α; r))$ prin setare $r_{1âÏ} = r$ (din intrarea sa).Apoi, algoritmul $\mathcal{A}$ alege o aleatorie $r_Ï$, și calculează $x_Ï = S(α; r_Ï)$ și $β_Ï = B(α, x_Ï) \oplus b_Ï$. In cele din urma, $\mathcal{A}$ alege o aleatorie $β_{1âÏ}$, invocă $D$ la intrare $(Ï, r_0, r_1; α,(β_Ï, β_{1âÏ}))$ și ieșiri $β_{1âÏ}$ dacă $D$ ieșirile 1 și $1âβ_1âÏ$ in caz contrar. Observați că dacă $\mathcal{A}$ presupuneri $β_{1âÏ}$ corect apoi invocă $D$ pe $(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α, x_{1âÏ})))$, iar altfel invocă $D$ pe $(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α, x_{1âÏ}) \oplus 1))$. Astfel, dacă
D iese 1, atunci $\mathcal{A}$ presupune că a ghicit $β_{1âÏ}$ corect (din moment ce $D$
iese 1 cu probabilitate mai mare atunci când este dat $B(α, x_{1âÏ})$ decât atunci când este dat $B(α, x_{1âÏ}) \oplus 1)$.
De ce în timp ce $\mathcal{A}$ alege a Aleatoriu $β_{1-Ï}$, când ghiceste incorect este ca $D$ este invocat cu $(Ï, r_0, r_1; α,(B(α, x_Ï) \oplus b_Ï, B(α, x_{1âÏ}) \oplus 1))$? De ce este $B(α, x_{1âÏ}) \oplus 1)$ echivalent cu un aleatoriu $β_{1-Ï}$?
