înregistrare Logare
Puncte:0
avatar Crypto

Detectați dacă două numere sunt egale fără a dezvălui informații suplimentare

drapel ma
Matteo Monti

Luați în considerare următorul scenariu. Alice alege un număr A; Bob alege un număr B. Atât A, cât și B aparțin unui set X relativ mic (prin mic, vreau să spun că X poate fi ușor de trecut în buclă: de dragul intuiției, imaginați-vă că X este de dimensiunea unui pachet de cărți). Mi-ar plăcea ca Alice și Bob să se angajeze într-un protocol care să le spună ambilor dacă A = B. Dacă A != B, atunci Alice nu ar trebui să aibă mai multe informații despre B, iar Bob nu ar trebui să aibă alte informații despre A.

Mă întreb dacă acest lucru este posibil? Dacă X ar fi foarte mare și presupunând fără pierderi de generalitate că A este prim, Alice ar putea alege un P prim arbitrar mai mare decât cea mai mare valoare din X și ar putea trimite A * P lui Bob. Bob ar putea încerca apoi să factorizeze A * P cu B: dacă funcționează, atunci A = B. Totuși, acest lucru presupune evident că este imposibil pentru Bob să încerce toate elementele lui X. Dacă X este mic, această presupunere scade imediat.

62
1 + 1
Perseids avatar
drapel na
Perseids
Aceasta se numește [problema milionarilor socialiști](https://en.wikipedia.org/wiki/Socialist_millionaire_problem) de altfel.
0
Răspunde
Puncte:3
poncho avatar Crypto
drapel my
poncho

Da, este foarte posibil.

Abordarea evidentă ar fi ca Alice și Bob să efectueze un protocol PAKE (Balanced Password Authenticated Key Exchange), cu $A$ și $B$ fiind „parolele” lor. Dacă vin cu același secret comun, $A=B$, iar dacă vin cu $A \ne B$ și ei nu învață nimic altceva despre $A$ și $B$

Există o serie de protocoale PAKE acolo; vezi articol wikipedia pentru unele dintre cele mai comune.

Un astfel de mod (care este simplificat CPACE) de a compara valorile $a$ cunoscut de Alice şi $b$ cunoscut de Bob ar fi să selecteze valori care nu au legătură $G$ și $N$ (Am scris acest lucru presupunând curbe eliptice; poate fi tradus direct într-un grup modp, cu excepția faptului că scăderea devine o inversare modulară) și:

  • Alice selectează o valoare aleatorie $r$ și calculează $C = r G + a N$; ea trimite $C$

  • Bob selectează o valoare aleatorie $s$ și calculează $D = s G + b N$; el trimite $D$

  • Alice calculează $S = r (D - a N)$; Bob calculează $T = s (C - b N)$; dacă $a=b$, atunci $S=T$; altfel nu au nicio legătură.

Alice și Bob pot trimite $S$ și $T$ unul față de celălalt (dacă au încredere în cealaltă parte pentru a fi sinceri) sau, alternativ, le folosesc pentru a genera chei de criptare și pentru a face un protocol simplu de verificare.

0 + 0
drapel romania
SEF 777
întrebarea această in alte limbi:

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.