Problema are o „soluție ușoară” folosind tehnici generale.
Există extensii ale problemei Milionarii lui Yao despre cum să calculezi în siguranță orice circuit $C(x, y)$. Acesta este un întreg domeniu de studiu, care se numește de obicei „Calcul Securizat” sau „Calcul Multiparty”.
Există circuite care pot sorta intrările care poartă numele de rețele de sortare. În timp ce există din punct de vedere tehnic $O(n \log n)$ cele (rețea de sortare AKS + sortare în zigzag), sunt complexe din punct de vedere tehnic, cu constante proaste, deci este aproape întotdeauna mai bine în practică să folosiți un $O(n (\log n)^2)$ rețea de sortare dintre care există multe (să spunem Batcher Odd-Even Mergesort).
Aceasta înseamnă că problema dvs. este rezolvată prin calculul unei rețele de sortare (să spunem Batcher Odd-Even Mergesort) folosind tehnici generale de calcul cu două părți.
Privind implementările protocoalelor MPC, se pare că acesta de la Universitatea din Boston include o demonstrație relevantă. În special, ei
- suma două matrice de intrare și apoi
- sortați rezultatul, folosind Bubblesort.
Probabil că puteți reutiliza o parte din acest cod, dar va trebui să fiți oarecum atenți.
Garanția de securitate a MPC este aceea
Protocolul MPC dezvăluie doar $C(x,y)$, de exemplu.este la fel de bun ca ambii participanți să își ofere contribuțiile $x, y$ unor terți de încredere $T$, care apoi calculează $C(x,y)$, și le spune răspunsul.
Ați putea, teoretic, să luați exemplul de cod de mai sus, să schimbați partea care însumează lucrurile la o concatenare și să continuați drumul. Acest lucru va duce la o schemă practic nesigură --- dat $x$ și $C(x,y)$, este banal de recuperat $y$.
În schimb, aș sugera să aveți $C(x,y)$ calculează (în reprezentarea sortată a concatenării $x||y$) un vector de biți care indică unde ar trebui să ajungă elementele fiecărei părți.
Aceasta încă codifică toate informațiile relevante despre comandă, dar ascunde intrarea fiecărei părți de la cealaltă parte (cu excepția informațiilor despre comandă, care „trebuie să curgă”).
Acest lucru se poate face prin
- Cartografierea fiecărui element $t$ de $x$ la 2t $,
- Cartografierea fiecărui element $t$ de $y$ la $2t+1$,
- concatenând aceste elemente transformate,
- sortarea concatenării,
- cartografiere $t\mapsto t\bmod 2$ la sfarsit.
Acest circuit calculează funcția pe care am descris-o anterior și „rupe legăturile” între ele $x$ și $y$ prin punerea elementului de $y$ mai târziu în vector. Această alegere este arbitrară.
Desigur, aceasta este ideea mea despre un circuit sensibil $C$ pentru a calcula care vă poate atinge obiectivele.
S-ar putea să credeți că scurge prea multe informații și că aveți un alt circuit pe care doriți să îl calculați.
Puteți utiliza în continuare tehnicile generale ale MPC pentru a face acest lucru --- cu condiția să specificați calculul pe care doriți să îl faceți.
În comentarii ați menționat dorința pentru o versiune multipartidă a acestui lucru.
Acest lucru este imediat din construcția de mai sus, dar îl voi discuta în mod explicit oricum.
Lăsa $P_0,\dots, P_{k-1}$ fii partide cu intrări $\vec x_0,\dots, \vec x_{k-1}$.
Definiți un circuit $C(x_0,\dots, x_{k-1})$ acea
- pentru fiecare $i$, aplică funcția $t\mapsto kt + i$ la fiecare coordonată a $x_i$,
- concatenează toate rezultatele împreună
- sortează rezultatele, de exemplu cu o rețea de sortare,
- calculează funcția $t\mapsto t\bmod k$ pe fiecare element al ieșirii.
Rezultatul va fi un vector cu elemente în $\{0,\dots,k-1\}$.
Pentru simplitate, spuneți că rezultatul este $[0,3,2,2,1,0,1,3]$.
Acest lucru ar indica tuturor celor 4 părți că ordinea relativă a intrărilor lor este
- cel mai mic element al partidei 0
- cel mai mic element al partidului 3
- cel mai mic element al partidului 2
- cel mai mare element al partidului 2
- cel mai mic element al partidului 1
- cel mai mare element al partidului 0
- cel mai mare element al partidului 1
- cel mai mare element al partidului 3.
Dacă se folosește o schemă MPC adecvată (cuvintele de căutat sunt „Calcul multipartit sigur în mod rău intenționat”), atunci acesta este, probabil, tot ceea ce va învăța un adversar, modulo câteva ipoteze tehnice. Aceste ipoteze depind de schema particulară pe care o utilizați, dar de obicei sunt ceva asemănător
- nu prea mulți participanți la protocol „se complică pentru a încălca protocolul”,
- adversarii sunt eficienți din punct de vedere computațional și
- poate că există o fază de „configurare de încredere”.
