Definesc calculul multipartit folosind paradigma ideală reală (vezi O introducere pragmatică în calculul multipartit securizat).
Adică, pentru orice atac de succes asupra unui protocol MPC în lumea reală, există un simulator care efectuează acest atac cu succes în lumea ideală. Rezultă că securitatea în lumea reală trebuie să fie echivalentă cu securitatea în lumea ideală.
Definesc sisteme interactive de demonstrare a cunoștințelor zero pentru o limbă $L$ folosind definiția originală din Complexitatea cunoștințelor sistemelor interactive de probă. Adică o pereche $(A, B)$ de mașini Turing interactive trebuie să îndeplinească
- Completitudine: dat $x \în L$, $B$ acceptă cu foarte mare probabilitate;
- Soliditatea: dat orice doveditor $A'$ și $x \nu\în L$ a trecut în $(A', B)$, $B$ acceptă cu probabilitate foarte mică;
- Zero-Knowledge: există un simulator probabilistic în timp polinomial care poate simula întregul schimb de mesaje între $A$ și $B$ pentru orice intrare $x \în L$.
Acum, hârtia Zero-Knowledge de la Secure Multiparty Computation mentioneaza urmatoarele:
Protocoalele cu cunoștințe zero pot fi privite ca un caz special de două părți securizate
calcul, în care funcția verifică validitatea unui martor deținut de probator.
Adică dat $L \in \mathcal{NP}$, există un algoritm $A$ astfel încât $x \in L \iff \exists w\colon A(x, w) = 1$ (definitia $\mathcal{NP}$).
O petrecere $P_1$ acționează ca doveditor, altul $P_2$ ca verificator.
$P_1$ stie $x$ și $w$, $P_2$ stie numai $x$.
Ei execută $A(x, w)$ împreună pentru a determina dacă $x \în L$ sau nu.
Clar, $w$ nu este dezvăluit verificatorului $P_2$ datorită protocolului MPC.
Cu toate acestea, nu este definiția cunoașterii zero mai generală?
Dacă doveditorul $P_1$ a trimis, dintr-un motiv oarecare, soluția la o instanță de an $\mathcal{NP}$- problema completa1, niciun simulator de timp polinomial nu ar putea simula această presupunere $\mathcal{P} \neq \mathcal{NP}$.
Sistemul de dovezi creat nu ar fi zero cunoștințe.
Deci, având în vedere că un protocol MPC ar putea face schimb de mesaje nesimulabile, un protocol MPC nu poate fi folosit de fapt pentru a implementa un sistem de verificare a cunoștințelor zero pentru o anumită limbă. $L \in \mathcal{NP}$, se poate?
1 Soluția poate fi făcută dependentă de $x$ astfel încât să nu fie constantă și astfel ușor de simulat.
