înregistrare Logare
Puncte:1
einsteinwein avatar Crypto

Logaritmul discret în modelul de grup generic este greu - Teorema lui Shoup

drapel st
einsteinwein

În binecunoscuta lucrare Shoups Limite inferioare pentru logaritmi discreti și probleme conexe el demonstrează că problema logaritmului discret este grea în modelul de grup generic (dacă operația de grup și inversul sunt singurele calcule care pot fi efectuate pe elementele grupului). Teorema 1 din lucrare spune că probabilitatea ca un algoritm generic $A$ rezolvă această problemă este delimitată de $\mathcal{O}(m^2/p)$ (m este numărul de interogări oracol, p ordinea grupului prim). Partea pe care nu o înțeleg este următoarea:

Dacă insistăm că $A$ reușiți cu probabilitate mărginită de o constantă pozitivă (de exemplu, 1/2) la mai jos, această teoremă se traduce într-o limită inferioară $\Omega(\sqrt{p})$ a numărului de operațiuni de grup interogate de $A$.

Poate cineva să-mi explice această concluzie?

132
0 + 0
ggm
Puncte:5
Ievgeni avatar Crypto
drapel cn
Ievgeni

Lăsa $K$ fi constanta (care nu depinde de $p$) astfel încât probabilitatea este mărginită de $K\frac{m^2}{p}$. (o asemenea, un asemenea $K$ există prin definiția lui $\mathcal{O}$).

Înseamnă că, dacă un adversar rezolvă problema logaritmului discret cu probabilitate mai mare decât $\frac{1}{2}$, noi obținem.

$$K\frac{m^2}{p}\geq \frac{1}{2}$$.

Implică faptul că

$$m\geq \sqrt{\frac{p}{2K}} $$

Astfel deducem că $m$ -care este de fapt o funcţie a $p$, este mărginită inferioară de $K'\sqrt{p}$, cu $K':=\sqrt{\frac{1}{2K}}$ o constantă care nu depinde de $p$.

Este echivalent cu a scrie $m\în \Omega(\sqrt{p})$ (in conformitate cu Notația Knuth).

Observă acum că $\sqrt{p}$ este exponențială în dimensiunea intrării și veți deduce că orice adversar generic nu este eficient împotriva DLog.

0 + 0
einsteinwein avatar
drapel st
einsteinwein
Mulțumesc foarte mult! :-)
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.