Nu văd nicăieri pe pagina respectivă care să descrie transferul neglijent în modul în care ați descris dumneavoastră.
Transfer neglijent:
- Alice ține două sfori $x_0, x_1$
- Bob ține puțin $b$
- Bob învață $x_b$ dar nu învață nimic despre $x_{1-b}$
- Alice nu învață nimic despre $b$
Circuit deformat:
- Când Alice garble un circuit boolean $f$, ea obține o mare colecție de texte cifrate $F$ („circuitul deformat”) și ea învață, de asemenea, două chei (etichete) pe fiecare fir al circuitului. Pe firul #$i$ ea învață $W_i^0$ care reprezintă fals pe acel fir și $W_i^1$ care reprezintă adevărat pe acel fir.
- Dacă Bob știe circuitul confuz $F$ si pentru fiecare intrare sârmă $i$ a circuitului din care știe exact unul $\{ W_i^0, W_i^1\}$ atunci poate a evalua circuitul deranjat să învețe exact o etichetă pe fiecare fir al circuitului (nu doar firele de intrare). El învață eticheta „corectă” a firului (adică cea corespunzătoare comportamentului lui $f$) pe fiecare fir, în funcție de care dintre etichetele de intrare începe.
- Pe măsură ce Bob evaluează circuitul deranjat, el nu învață dacă ține $W_i^0$ sau $W_i^1$ pentru orice fir $i$. Cu alte cuvinte, el nu știe dacă vreun fir din circuit poartă adevărat sau fals. El evaluează circuitul „orb”.
Dacă Alice și Bob doresc să evalueze o funcție utilizând circuite deformate, atunci Alice deranjează circuitul și trimite circuitul deranjat $F$ lui Bob.
Dar Bob trebuie să învețe și pentru fiecare intrare sârmă $i$ în circuit, exact unul dintre $\{ W_i^0, W_i^1\}$.
Atât Alice, cât și Bob au intrări la acest calcul.
Dacă firul #$i$ este unul dintre firele de intrare ale lui Alice, atunci ea îl poate trimite pe cel „corect” de la $\{W_i^0, W_i^1\}$, deoarece le știe pe ambele și își cunoaște bitul de intrare pe acel fir.
Dacă firul #$i$ este unul dintre firele de intrare ale lui Bob, trebuie să existe o cale pentru Bob alege pentru a învăța exact unul dintre $\{W_i^0, W_i^1\}$.
Deoarece Bob alege între aceste valori în funcție de intrarea sa privată, Alice nu ar trebui să învețe pe care a ales-o.
Transferul neglijent este folosit exact pentru acest pas.
Pentru firul de intrare #$i$ aparținând intrării lui Bob, furnizează Alice $W_i^0$ și $W_i^1$ la un exemplu de transfer neglijent, iar Bob alege pe care dintre acestea să învețe.
Există variante de transfer neglijent unde are Alice $N$ șiruri și Bob alege unul dintre ele pentru a învăța.
Dacă Alice și Bob vor să calculeze o funcție foarte simplă $f(a,b)$, unde sunt numai $N$ posibile intrări pentru Bob ($b \in \{1, \ldots, N\}$), atunci da, pot folosi transferul neglijent pentru a calcula funcția direct, așa cum sugerați dvs., fără circuite deranjate.
Alice folosește $f(a,1), f(a,2), \ldots, f(a,N)$ ca intrări pentru transferul neglijent.
Bob alege să învețe $b$a dintre acestea, care este $f(a,b)$.
Acest lucru funcționează doar când $N$ este foarte mic, deoarece necesită comunicare și calcul proporțional cu $N$.
Sa nu uiti asta $N$ este numărul de intrări posibile pentru Bob.
Dacă există un circuit în care are Bob $k$ fire de intrare, atunci are $N=2^k$ posibile intrări.
Prin urmare, de obicei, Bob are prea multe intrări pentru a utiliza această abordare.
Răspuns la postarea editată:
Abordarea ta pentru problema milionarului nu este tocmai clară, așa că trebuie să ghicesc câteva lucruri.
Nu funcționează să dezvăluie informații parțiale despre intrări în timpul protocolului.
Dacă Alice are intrarea 1, ea nu ar trebui să poată distinge între Bob care are intrarea 2 și intrarea $2^{20}$ -- dar aceste două intrări ar arăta foarte diferit dacă rezultatele comparațiilor ar fi dezvăluite în mod clar.
Având în vedere acest lucru, sugerați să criptați lucrurile cumva. Dar, în esență, propuneți o căutare binară. O căutare binară necesită să cunoașteți rezultatul comparațiilor anterioare pentru a decide ce comparație să faceți în continuare. Dacă criptați rezultatul comparațiilor, atunci nu este clar cum să procedați în rundele următoare.
O mare problemă cu propunerea dvs. este că este în mod inerent secvenţial. Părțile nu își pot cunoaște intrările în runda următoare până când nu primesc rezultate din runda anterioară.
Prin urmare $k$ comparații de care aveți nevoie $\Theta(k)$ runde de comunicare.
Comparați acest lucru cu o abordare bazată pe GC, care necesită întotdeauna un număr constant de runde de comunicare.
Cred că ai o conexiune conceptuală bună, totuși.
Imaginează-ți funcția $f$ este foarte mic, astfel încât este posibil să scrieți întregul tabel de adevăr al $f$.
Sa spunem $f : \{1,2,3,4\}^2 \la \{0,1\}$.
Alice alege chei de criptare aleatorii $A_1, \ldots, A_4$ și $B_1, \ldots, B_4$.
Ea criptează, de asemenea, tabelul de adevăr al $f$ la fel de
$$\textsf{Enc}( A_1 \| B_1, f(1,1)), ~~
\textsf{Enc}( A_1 \| B_2, f(1,2)), ~~\ldots,
\textsf{Enc}( A_i \| B_j, f(i,j)), ~~\ldots$$
A evalua $f$ pe intrările lor private, Alice poate trimite toate aceste texte cifrate lui Bob.
Ea poate trimite corect $A_i$ valoare și pot folosi 1-din-4 OT pentru a-i permite lui Bob să învețe corect $B_j$ valoare.
Acum Bob poate decripta exact unul dintre aceste texte cifrate, care va conține rezultatul corect al $f$.
Circuitele distorsionate sunt exact ceea ce obțineți atunci când luați această construcție simplă, dar în loc să criptați rezultatul final al funcției, criptați cheile pentru un alt gadget de același tip.
