Puncte:1

Legătura dintre Diffie-Hellman decizional, logaritmul discret și cunoașterea ipotezelor exponenților

drapel yt

Sunt curios despre relația dintre logaritmul discret și Diffie-Hellman decizional. Este sigur să existe o presupunere ca următoarea pentru a lega cele două?

Dat g^x și g^y aleși în mod uniform și independent, dacă există un algoritm eficient care poate distinge g^(xy) și g^r aleatoriu cu probabilitate neneglijabilă, atunci există un extractor care poate extrage x sau y cu probabilitate deloc neglijabilă?

Aceasta arată ca o ipoteză a Cunoașterii exponentului, cu toate acestea, vreau să abordeze problema decizională. De asemenea, se știe că unele grupuri de curbe eliptice ar putea folosi împerecherea pentru a rupe DDH, în acest caz, vom restricționa discuția la grupuri precum grupul de reziduuri cuadratice peste numere întregi Blum.

Puncte:0
drapel cn

Cred că realizarea acestei legături nu este deloc obișnuită.

Un motiv bun este că, de exemplu, un grup biliniar cu împerechere simetrică (Tipul 1) poate fi considerat sigur pentru ipoteza de log discret, dar nu va fi niciodată cazul pentru ipoteza DDH.

Daca primesti $(g,x,y,z)$, puteți verifica cu ușurință dacă $e(g,z)=e(x,y)$, iar această egalitate este suficientă pentru a decide dacă este un tuplu Diffie-Hellman sau nu.

Pentru a vedea un motiv mai teoretic, puteți privi ipoteza Gap-DH (în această problemă adversarul trebuie să rezolve o instanță CDH cu un oracol DDH): Astfel, s-a demonstrat că dacă pentru orice adversar algebric, dacă DLog este valabil, atunci Gap-DH este, de asemenea, o problemă grea (astfel, dacă înlocuiți o instanță CDH cu o instanță DLog, aceasta devine și mai dificilă).

Puteți căuta acest doctorat pagina 136 pentru mai multe detalii

https://www.iacr.org/phds/index.php?p=detail&entry=1476

Și pentru că luând în considerare adversarul algebric mi s-a părut echivalent cu ipoteza Cunoașterii exponentului, astfel ar fi foarte ciudat să faci o astfel de legătură (din câte am înțeles, va implica că Dlog este ușor, dar nu sunt complet sigur de acea).

Sean avatar
drapel yt
Mulțumesc pentru informații!
Sean avatar
drapel yt
Acum, ce se întâmplă dacă limităm discuția la acele grupuri în care se consideră că problema DDH este dificilă (de exemplu, acele grupuri non-Gap_DH)?
Ievgeni avatar
drapel cn
Nu înțeleg ce vrei sa spui. Dar nu ezita să pui o nouă întrebare cu o altă postare, ar fi mai clar.
Sean avatar
drapel yt
Am mai postat o întrebare ca mai jos. Acest lucru explică de ce trebuie să-l conectez la ipoteza Knowledge of Exponent.
Sean avatar
drapel yt
Link-ul este mai jos: https://crypto.stackexchange.com/questions/91834/decisional-diffie-hellman-assumption-over-group-of-quadratic-residue

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.