înregistrare Logare
Puncte:3
Sean avatar Crypto

Ipoteza decizională Diffie-Hellman asupra grupului de reziduuri cuadratice

drapel yt
Sean

Luați în considerare decizia Diffie-Hellman (DDH) terminată $QR_n$ (grupul de reziduuri pătratice peste $n=pq$ Unde $p$ și $q$ sunt numere prime sigure). Conform lucrării lui Boneh, DDH ar trebui să fie greu peste $QR_n$ (https://link.springer.com/chapter/10.1007/BFb0054851):

[DDH] Dat fiind trei eșantionate aleatoriu $g^x, g^y, g^z$ este greu de spus dacă $z = x*y$.

Mă întreb: dacă i se oferă un plus $x^2$ $mod$ $n$, această problemă este încă greu de rezolvat $QR_n$? (Intuiția este că calculând rădăcina lui $x^2$ este greu, astfel încât intuitiv acest pătrat nu ar trebui să ofere informații suplimentare pentru rezolvarea DDH. Excepțiile ar putea fi că scurgeri de simboluri Jacobi/Legendre, dar alegerea aleatorie a $z$ poate fi reparat corespunzător?).

109
0 + 8
Ievgeni avatar
drapel cn
Ievgeni
dat $x^2$ sau $g^{x^2}$?
1
Răspunde
poncho avatar
drapel my
poncho
„deci intuitiv acest pătrat nu ar trebui să scurgă informații suplimentare”; de fapt, din punct de vedere al demonstrabilității, este invers - dacă ar fi ușor de calculat, nu ar scurge nimic (atacatorul ar putea să o calculeze el însuși, prin urmare, a da valoarea atacatorului nu îi spune nimic din ceea ce face." nu stiu deja). Cel mai evident contraexemplu, valoarea $g^{xy}$ este, de asemenea, greu de calculat, dar și acea valoare face ca problema atacatorului să fie trivială. Nu spun că darea valorii $g^{x^2}$ facilitează problema atacatorului; Spun că nu este banal să arăți.
0
Răspunde
Sean avatar
drapel yt
Sean
Dat $x^2$ (nu $g^{x^2}$). Deci întrebarea mea este: dacă i se oferă acest $x^2$ suplimentar, decizia DH ar fi încă grea (în contextul grupului de reziduuri pătratice)
0
Răspunde
Ievgeni avatar
drapel cn
Ievgeni
dar, putem calcula cu ușurință rădăcinile pătrate ale lui $x^2$ în $\mathbb{R}$ și una dintre aceste rădăcini va fi egală cu $x^2$. Astfel, este ușor să verificați dacă este un ddh-tuplu sau nu.
0
Răspunde
Geoffroy Couteau avatar
drapel cn
Geoffroy Couteau
Interesanta intrebare! Nu văd nicio reducere evidentă la ipotezele standard. O sugestie: ați putea începe prin a lua în considerare o versiune simplificată a problemei, unde dat $x^2 \bmod \phi(n)/4$, sarcina dvs. este să distingeți $g^x$ de un element aleatoriu de $\mathsf {QR}_n$.
0
Răspunde
Sean avatar
drapel yt
Sean
În ceea ce privește comentariul lui Levgeni: Dar în $QR_n$, acest $n$ este compusul RSA, atunci încercarea de a găsi rădăcina unui reziduu pătratic este echivalent cu factorizarea $n$. Vezi lucrarea lui Couteau eurocrypt17, de exemplu: https://link.springer.com/chapter/10.1007/978-3-319-56614-6_11.
0
Răspunde
Sean avatar
drapel yt
Sean
Iată o întrebare similară pe care am postat-o ​​ieri: -- are vreo diferență faptul că modulul este $\phi(n)/4$ sau $n$? https://crypto.stackexchange.com/questions/91786/group-of-quadratic-residue-over-blum-integer
0
Răspunde
Sean avatar
drapel yt
Sean
Văd punctul de $\phi(n)/4$ acum -- pentru $x$ pe exponentul $g^x$. Dificultatea aici este că, dacă se expune totientul $\phi(n)$, $n$ ar fi apoi factorizat. Ceea ce am putea face este să cerem unui server de încredere să furnizeze $r \phi(n)$ unde $r$ este un întreg mare aleatoriu. În acest fel, se oferă un $x^2$ congruent peste $r \phi(n)$. Astfel, problema este ușor modificată în: \n Având în vedere $x^2 \mod \phi(n)/4*r$ unde $r$ și $\phi(n)$ sunt necunoscute, este posibil să distingem $g^ x$ cu un algoritm eficient?
0
Răspunde
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.