Puncte:1

Protocolul de intersecție a seturilor private bazat pe Diffie-Hellman nu poate trece dovada de simulare?

drapel vn

Având în vedere popularul protocol de intersecție a seturilor private (PSI) descris mai întâi în [1]:

  • Alice alege un aleatoriu $a$, și trimite $\{H(x_i)^{a}\bmod p\}| (i=1,...m)$ lui Bob.
  • Bob alege un aleatoriu $b$, și trimite $\{H(y_i)^{b}\bmod p\}| (i=1,...n)$ lui Alice.
  • Alice calculează și trimite $\{H(y_i)^{ba}\bmod p\}| (i=1,...n)$ lui Bob.
  • Bob calculează și trimite $\{H(x_i)^{ab}\bmod p\}| (i=1,...m)$ lui Alice.
  • Fiecare parte calculează local intersecțiile.

Intrebarea 1: Dacă (cu o șansă foarte mică) există $x_1$ și $x_2$ acea $H(x_1)=H(x_2)^2\bmod p$, atunci Bob l-a putut descoperi pentru că $H(x_1)^a=(H(x_2)^a)^2\bmod p$. Cu siguranță Bob nu a putut simula această informație. Înseamnă că acest protocol încalcă securitatea semi-onest?

Am discutat despre asta cu prietenii, unii au spus că acest lucru nu încalcă securitatea semionest, deoarece șansa de a $H(x_1)=H(x_2)^2\bmod p$ este neglijabil. Dar cred că da, pentru că în Definiția 4.1.din tutorialul de demonstrare a simulării [2], simularea ar trebui să reușească întotdeauna și nu ar trebui să depindă de intrare $\{x,y\}$.

Intrebarea 2: În protocolul PSI (Fig.3) din [3], ei folosesc $H(H(x_i)+H(x_i)^{a})$ în loc de $H(x_i)^{a}$ (observați că protocolul este încă corect dacă folosesc $H(x_i)^{a}$), acest lucru pare să-mi întărească punctul (protocolul naiv DH-PSI nu este demonstrabil), deoarece $H(H(x_i)+H(x_i)^{a})$ este mai ușor de simulat decât $H(x_i)^{a}$ . Este corectă înțelegerea mea?

Mulțumiri.

  1. Huberman B A, Franklin M, Hogg T. Creșterea confidențialității și a încrederii în comunitățile electronice[C]// Conferința ACM privind comerțul electronic. ACM, 1999:78-86
  2. Lindell Y, Cum să o simulezi, https://eprint.iacr.org/2016/046.pdf
  3. Heinrich A, Hollick M, Schneider T, et al. PrivateDrop: Autentificare practică pentru păstrarea confidențialității pentru Apple AirDrop, USENIX'SEC 21
Puncte:1
drapel us

Dacă (cu o șansă foarte mică) există $x_1$ și $x_2$ acea $H(x_1) = H(x_2)^2$, atunci Bob ar putea descoperi... simularea ar trebui să reușească întotdeauna și nu ar trebui să depindă de intrare $\{x,y\}$.

Sunt de acord cu prietenul tău că această observație nu încalcă securitatea semi-onest.

În modelul semi-onest, intrările sunt independente de oracolul aleatoriu. Cu alte cuvinte, intrările sunt fixe primul, și apoi $H$ este eșantionată. Mediul nu are acces la oracolul aleatoriu (în modelul de oracol aleatoriu local), așa că alegerea sa de intrări pentru părțile cinstite nu depinde de oracolul aleatoriu. Deci evenimentul care $H(x_1) = H(x_2)^2$ nu depinde de $x_1, x_2$. Este neglijabil probabil pentru toate intrările, astfel încât simulatorul poate ignora acest caz în siguranță.

În protocolul PSI (Fig.3) din [3],

Nu sunt sigur care este întrebarea ta aici. În [3] au nevoie de un protocol PSI malițios-securizat, iar protocolul clasic DH-PSI nu este. Deci folosesc protocolul mai complicat al lui Jarecki & Liu.

Întrebarea mai mare pare să fie dacă DH-PSI clasic „nu poate fi simulat”, unde probabil că te referi împotriva adversarilor rău intenționați. Sunt de acord. Gândiți-vă doar la cazul în care părțile au câte 1 articol. Luați în considerare cazul în care o Alice coruptă interoghează oracolul aleatoriu la $x_0$ și $x_1$, aruncă o monedă $b$, și trimite $H(x_b)^a$ pentru exponent aleatoriu $a$. Exponentul aleatoriu $a$ face vizualizarea simulatorului (interogări aleatorii ale oraclelor $x_0, x_1$ și mesaj de protocol $H(x_b)^a$) perfect independent de $b$. Dar simulatorul trebuie să ghicească $b$ pentru a extrage corect.

Postează un răspuns

Majoritatea oamenilor nu înțeleg că a pune multe întrebări deblochează învățarea și îmbunătățește legătura interpersonală. În studiile lui Alison, de exemplu, deși oamenii își puteau aminti cu exactitate câte întrebări au fost puse în conversațiile lor, ei nu au intuit legătura dintre întrebări și apreciere. În patru studii, în care participanții au fost implicați în conversații ei înșiși sau au citit transcrieri ale conversațiilor altora, oamenii au avut tendința să nu realizeze că întrebarea ar influența – sau ar fi influențat – nivelul de prietenie dintre conversatori.