Puncte:0

Indistincbilitatea calculului folosind ipoteza DDH

drapel tm

Aceasta face parte din explicația schemei de angajament de la DDH în aceste note de curs ale lui Vipul Goyal: https://www.cs.cmu.edu/~goyal/s18/15503/scribe_notes/lecture22.pdf

Întrebarea mea nu este direct legată de conținutul pdf-ului, dar la pagina 20-4, scrie $\{g, g^a, g^b, m \cdot g^r |(a, b, r) \leftarrow \mathbb{Z}_q\}$ nu se poate distinge din punct de vedere computațional de $\{g, g^a, g^b, g^r |(a, b, r) \leftarrow \mathbb{Z}_q\}$. De ce este neapărat adevărat? Poate cineva să explice oficial de ce este așa? De asemenea, atunci când textele descriu distribuțiile în acest fel, sunt cele două $(a, b, r)$â este egal în cele două distribuții? Sau este doar că simbolurile sunt aceleași, dar de fapt sunt selectate în mod independent la întâmplare din $\mathbb{Z}_q$?

Mulțumiri.

drapel us
Bună, bun venit la crypto.stackexchange. Sunt confuz deoarece pagina 20-4 are literalmente o justificare pas cu pas a motivului pentru care aceste două distribuții nu se pot distinge. Există un pas mai specific care nu are sens?
user658183 avatar
drapel tm
Nu eram sigur de ecuația care este între „Dar” și „Deci avem” de la pagina 20-4, dar cred că răspunsul lui yacovm a ajutat.
Puncte:2
drapel us

Ei bine, asta $m$ este un element din grup $\mathbb{G}$ deci exista unele $\alpha \in \mathbb{Z}_q$ astfel încât $m=g^{\alpha}$, prin urmare $m \cdot g^r = g^{\alpha+r}$ și observă că din moment ce $r$ este selectat uniform la întâmplare din $\mathbb{Z}_q$, apoi distribuirea de $\alpha + r$ este exact (nu doar din punct de vedere computațional, ci exact) uniform în $\mathbb{Z}_q$ de asemenea.

Intuitiv te poți gândi la $r+\alpha$ ca luare $\alpha$ pe care cineva la selectat pentru tine și apoi adăugându-i un număr aleator modulo $q$, și este exact uniform deoarece pentru fiecare rezultat posibil al $r+\alpha$ există exact un singur $r$ asta face ca rezultatul, deci este uniform.

În ceea ce privește (a,b,r) - rețineți că ipoteza DDH încearcă să spună ceva de genul: Dacă vă uitați la două elemente aleatoare ale grupului $g^a, g^b$ și aveți un al treilea element de grup $h\in\mathbb{G}$, atunci nu știi dacă $h=g^{a\cdot b}$ sau asta $h$ este un element de grup complet aleatoriu, fără legătură $g^r$ pentru unii aleatoriu $r$. Modul în care scrieți acest lucru este să vă uitați la două distribuții în care $g^a, g^b$ sunt aceleași în ambele părți ale egalității, dar al treilea element este diferit (este oricare $g^{a \cdot b}$ sau $g^r$ și spuneți că în ipoteza DDH, nu există o mașină de turnare a timpului polinomială probabilistică eficientă care să poată distinge între $g^{a \cdot b}$ și un element de grup aleatoriu.

user658183 avatar
drapel tm
Mulțumiri! Ce zici de a doua întrebare? În astfel de notații, sunt $a, b, r$ valori egale pentru cele două distribuții sau sunt alese aleatoriu separat?
yacovm avatar
drapel us
Am actualizat răspunsul, spune-mi dacă este clar acum.
user658183 avatar
drapel tm
Da, am inteles raspunsul tau. Mulțumesc mult!
yacovm avatar
drapel us
Nicio problemă, vă ajut cu plăcere

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.