înregistrare Logare
Puncte:2
Rory avatar Crypto

Ruperea CDH rupe și DHI

drapel mp
Rory

Încerc să arăt asta prin ruperea Ipoteza de calcul Diffie-Hellmann (CDH). se rupe de asemenea Ipoteza inversă Diffie-Hellmann. Din păcate, sunt puțin blocat și nu știu unde să merg. Bănuiesc că proprietatea de bilinearitate din grupul de împerechere dat de $PGGen$ este de vină, dar nu știu sigur cum să abordez problema în continuare. Definițiile sunt cele de mai jos.

Cu Diffie-Hellman computațional (CDH) definit de un advarsery PPT A unde: $Adv^{cdh}_{PGGen,A}(n)$ este neglijabilă și:

$Adv^{cdh}_{PGGen,A}(n) := Pr[Z = g^{xy} \mid PG \stackrel{$}{\gets} PGGen(1^n); x, y \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x, g^y)]$

și ipoteza inversă Diffie-Hellmann (DHI) definită de un adversar PPT A unde: $Adv^{q-dhi}_{PGGen,A}(n)$ este neglijabilă și:

$Adv^{q-dhi}_{PGGen,A}(n) := Pr[Z = g^{1/x} \mid PG \stackrel{$}{\gets} PGGen(1^n); x, y \stackrel{$}{\gets} \mathbb{Z}_p ; Z \stackrel{$}{\gets} A(PG, g^x)]$

Orice ajutor ar fi foarte apreciat.

83
0 + 0
Puncte:3
Ievgeni avatar Crypto
drapel cn
Ievgeni

Dacă puteți sparge CDH, înseamnă că puteți crea eficient toate $g^{x^u}$ pentru toți $i$ pozitive, prin combinarea exponentierii rapide cu un oracol CDH.

$$g^{1/x} = \begin{cases} EXP(G',u) = g & \text{if } u=0 \ EXP(CDH(G'),u/2) & \text{dacă } u \text{ este par}\ CDH(G', EXP(G',u-1)) & \text{dacă } u \text{ este impar}\ \end{cazuri}$$

Apoi, putem calcula $g^{x^{p-2}}= g^{x^{p-2} \mod p}= g^{x^{p-2}}= g^{\frac{1}{x } \mod p}$. Apoi puteți sparge DHI.

0 + 0
kelalaka avatar
drapel in
kelalaka
Cred că cel mai simplu mod este să arăți că DHI este echivalent cu Square DH...
0
Răspunde
poncho avatar
drapel my
poncho
@kelalaka: totuși, lucrul bun cu abordarea $g^{x^{q-2}}$ este că funcționează curat chiar dacă Oracleul tău este fixat la un anumit $g$
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.