În primul rând, nu am văzut până acum această definiție a ipotezei DDH. Probabil este ceva ca o presupunere Hashed-DDH. Dacă cineva are de adăugat mai multe informații sau un răspuns mai bun, aș fi bucuros să citesc despre asta. Voi răspunde la întrebare fără a lua în considerare existența $H$. Cu toate acestea, voi răspunde la notația folosită pentru a-l defini.
În primul rând, care este semnificația asteriscului în $H:\{0,1\}^ââ\{0,1\}^k$?
Este folosit pentru a defini o funcție hash $H$ care ia ca intrare un șir binar de lungime arbitrară și returnează un șir binar de lungime constantă. The $*$ simbolul este Steaua Kleene.
PPT
Înseamnă algoritm de timp polinomial probabilist.
În al treilea rând, de ce dacă $b=1,sâH(gab)$, altfel $sâ{0,1}^k$? Înțeleg pasul 1,2,3, dar nu înțeleg pasul 4,5,6
Aici DDH, este definit în termeni de Indistinguishability Game (IND-Game). Produce două distribuții de probabilitate bazate pe dacă $b$ este $0$ sau $1$. Dacă $b=0$ apoi a adversarului $M$ intrarea este $(\mathcal{G}', g, q, H, g^{a}, g^{b}, g^{ab})$ altfel dacă $b=1$ aportul adversarului este $(\mathcal{G}', g, q, H, g^{a}, g^{b}, s \overset{\$}{\leftarrow} \{0,1\}^k) $. După cum puteți vedea, singura diferență la intrările adversarului este ultimul argument. Definiția consideră intrarea adversarului ca distribuții de probabilitate și presupune că aceste distribuții nu pot fi distinse pentru adversarii PPT sau, echivalent, că distanța lor statistică este neglijabilă pentru adversarii PPT.
