Atacul revendicat nu „rupe” criptografia bazată pe rețea, ci doar îmbunătățește și mai mult atacurile cunoscute.
Voi încerca să descriu pe scurt situația.
Asimptotice:
Asimptotic, cel mai bun indiciu al nostru este că LWE necesită timp $2^{cn}$ pentru a rezolva o constantă $c$.
Acest lucru trebuie să fie în contrast cu RSA $2^{(\log N)^{1/3}}$ (acest lucru este foarte imprecis și ar trebui să fie utilizat în mod corespunzător Notația L), și curba eliptică DLog $2^{\frac{1}{2}\log_2|\mathbb{G}|}$.
Asta înseamnă că, chiar și cu îmbunătățirile aduse atacurilor împotriva variantelor LWE, credem că are o „scalare mai bună” decât ipoteze precum RSA (pe care o menționezi în mod special), deși similar cu ECDlog.
Estimările curente ale $c$ poate varia, dar este $< 1/2$ (Cred, poate $\aproximativ 0,28 $ este curent, dar nu s-a verificat), deci ECDlog este cel mai bun pe această metrică, apoi LWE și apoi (departe în distanță) RSA/câmp finit DH.
De asemenea, nu este clar cât de utilă este această noțiune practic --- spune asta niste setul de parametri poate fi sigur, dar nu ajută la alegerea pe care.
Concret:
Chiar dacă LWE face lua $2^{cn}$ timpul să rezolvăm, asta nu ne ajută dacă nu știm $c$.
Atacurile îmbunătățite s-au îmbunătățit (teoretic). $c$ peste orar.
Acest lucru poate duce la „ruperea” diferitelor seturi de parametri (deși nu în sensul că putem realiza atacuri practice împotriva lor --- în sensul că nu îndeplinesc standardele minime ale NIST pentru a fi într-un anumit „nivel de securitate”).
Această situație este, fără îndoială mai bine decât situația prin care a trecut factoringul odată cu dezvoltarea tehnicilor de „calcul indicelui”.
Pentru ECDlog, cele mai bune atacuri sunt încă (variantele) algoritmului Pollard Rho, și așa a fost pentru un lung timp.
Toate acestea înseamnă că ECDlog are în mod concret cea mai bine înțeleasă securitate, deși aș spune că LWE încă bate RSA/alte lucruri vulnerabile la tehnicile de calcul index.
În timp ce NFS a fost creat în urmă cu aproximativ 30 de ani, este încă plauzibil că este îmbunătățit.
De exemplu, drumul câmpului finit (caracteristic mic) DLog a fost de la aproximativ aceeași complexitate ca RSA, până la (aproximativ) $2^{(\log p^n)^{1/4}}$, iar apoi la timp cvasipolinomial (cf Nadia Heninger, prin Matthew Green).
Acest lucru nu înseamnă că se va întâmpla ceva similar cu factoring (nu s-a întâmplat de aproximativ 30 de ani), dar poate că este încă o posibilitate incomodă.
Practic:
Ultimul mod de a înțelege securitatea unei ipoteze de duritate este de a rezolva cazuri foarte mari ale acesteia.
Acest lucru duce la întrebări
- care este cel mai mare set de parametri care au fost sparți într-un calcul real?
- cât timp a fost investit în acest calcul?
Pentru RSA, lucruri precum RSA-240 (un semiprime de 768 de biți) au fost sparte în 1000 de ani de bază (sau 6 luni de perete iirc).
În acest sens, RSA (și DH cu câmp finit pentru caracteristica non-mică) este ipoteza noastră de duritate cel mai bine testată (și poate cel mai bine înțeleasă).
Curbele eliptice au avut, de asemenea, calcule lungi.
The pagina de înregistrări enumeră un număr de pauze în gama de grupuri de mărime $2^{110}$ la $2^{120}$, iar orele de ceas de perete sunt din nou de până la 6 luni la nivelul superior.
Pe această măsură, LWE rămâne într-adevăr în urmă.
Există câteva „provocări latice” bine-cunoscute (a la provocările RSA), de exemplu TU Darmstadt provocări.
Acestea sunt pentru LWE simplu (Peikert a făcut unele pentru RLWE, dar nu văd un clasament public pentru ei).
Oricum, pentru provocările simple LWE, cea mai înaltă dimensiune pe care cineva a rezolvat-o vreodată este 85, în timp ce dimensiunile 500+ (deși 700+ sunt mai frecvente) sunt folosite în schemele practice.
Toate înregistrările la care m-am uitat au folosit mai puțin de 200 de ore de ceas de perete (de obicei pe o mână de procesoare), așa că calculele sunt într-adevăr mult la scară mai mică decât calculele RSA/ECDlog.
Acest lucru înseamnă că „atacurile mari” împotriva LWE sunt cu cel puțin un ordin de mărime mai mici decât atacurile similare împotriva RSA/ECDlog, deși acest lucru probabil subsăvește masiv dimensiunea atacurilor academice moderne împotriva RSA.
Deci, cea mai mare instanță de LWE care a fost spartă este mică (ceea ce este un bun indiciu de securitate), și nu a avut încă „atacuri cu adevărat mari” montate împotriva sa (care este unul rău).
Cele de mai sus ignoră multe subtilități despre ipotezele de duritate, cum ar fi
- rezistenta la scurgeri,
- ușurință de implementare,
- ușurința atenuării canalelor laterale.
De fapt, LWE se descurcă destul de bine cu toate aceste valori (atâta timp cât nu faci semnături), cu siguranță mai bine decât RSA, totuși nu știu personal pentru ECDlog.
Acestea fiind spuse, eu personal văd LWE ca
- A masiv îmbunătățirea RSA/(câmp finit)DLog și
- poate mai rău decât ECDlog.
Cu siguranță, dacă computerele cuantice nu ar fi un risc, nu ar exista niciun motiv să te îndepărtezi de ECDlog (cu excepția aplicațiilor de specialitate precum FHE).
Dar ei sunt, așa că trebuie.
Din această perspectivă, comparațiile nu ar trebui să fie între LWE și RSA/ECDlog, deoarece, din păcate, lumea în care au sens ne părăsește rapid.
În schimb, comparațiile ar trebui să fie cu alte ipoteze post-cuantice.
Dar printre ipotezele post-cuantice, LWE este într-adevăr spre vârf.
Există ipoteze care au o securitate mai bună (cum ar fi McEliece), dar eficiența lor este prea proastă pentru a fi utilizabile, cu excepția cazurilor speciale.
Principalele alte ipoteze fezabile sunt
- NTRU, care este, de asemenea, bazat pe zăbrele și, prin urmare, nu este cu adevărat „independent” de atacurile asupra LWE și
- SIDH.
SIDH în sine este încă cu un ordin de mărime mai lent decât construcțiile bazate pe zăbrele iirc (deși este mai compact).
Există câteva motive pentru a susține că securitatea sa a „rezistat mai bine testului timpului” decât ipotezele bazate pe zăbrele (cf. Carcasa pentru SIKE), dar și iirc de numai ~10 ani, deci este încă o ipoteză nouă (și a fost și mai mult în 2016, când NIST și-a început procesul de selecție).
De asemenea, este destul de complex din punct de vedere matematic, ceea ce poate face dificile implementările (dar nu am încercat).
Acest lucru este oarecum lung (și ignoră multe subiecte tehnice, să spunem duritatea „modulelor mici” LWR sau afirmațiile despre impactul dimensiunilor grupurilor de galois asupra durității RLWE, care au fost nerezolvate de ani de zile.
Acestea sunt subiectele în care par cel mai probabil să fie posibile „marele pauze”, dar încă nu s-a întâmplat nimic), dar sper că începe să răspundă măcar la întrebarea ta.
