În primul rând, ar trebui să fie clar că se poate crește oricând zgomotul într-o instanță LWE fără a afecta securitatea, astfel încât (pentru modul fix) raportul modul/zgomot mai mare implică securitate „nu mai proastă”.
Desigur, acest lucru nu explică de ce securitatea ar trebui să varieze în ceea ce privește $\sigma/q$, în loc de o expresie mai complicată.
Există două motive pentru a vedea de ce aceasta este modalitatea „corectă” de a măsura dimensiunea zgomotului.
Primul este că este ceea ce apare în cel mai rău caz până la reducerea medie.
De exemplu, Reducerea inițială a lui Regev arată că:
Teorema 1.1 (informală) Lăsa $n, p$ fie numere întregi și $\alpha\in(0,1)$ fie astfel încât $\alpha p >2\sqrt{n}$. Dacă există un algoritm eficient care să rezolve $LWE(p, \Psi_\alpha)$ atunci există un algoritm cuantic eficient care aproximează versiunea de decizie a problemei celei mai scurte vectori (GAPSVP) și cea mai scurtă problemă a vectorilor independenți (SIVP) în interior $\tilde{O}(n/\alpha)$ în cel mai rău caz.
Rețineți că $1/\alpha$ este raportul „modul la zgomot”, deci factorul de aproximare pe care trebuie să presupunem că este greu de scalat direct $1/\alpha$.
În practică, totuși, nu se dorește să apeleze în mod concret la reducerile de la cel mai rău caz la cel mai mediu atunci când alegeți parametrii, din două motive:
$\sigma := \alpha q > 2\sqrt{n}$ este necesar, deci pentru $n> 500$ (care este o limită inferioară confortabilă) de care avem nevoie $\sigma > 40$, mult mai mare decât folosesc oamenii în practică.
În plus, există un „decalaj de etanșeitate” în reducerea, a se vedea secțiunea 6 din O altă privire asupra etanșeității 2). Acest lucru afectează doar „constantele” în reducere, dar impactul este destul de mare, iar pentru a face apel la reducere trebuie să alegeți parametri destul de ineficienți.
Așadar, cum putem spune că în mod concret acel raport mai mic modulul-zgomot în LWE implică o securitate mai bună?
Există două puncte aici:
Modulul LWE nu afectează foarte mult securitatea acestuia, vezi, de exemplu, cor 3.2 din Duritatea clasică a LWE.
Puteți parametriza în mod explicit atacurile cunoscute în ceea ce privește raportul modul-zgomot, vezi capitolul 4 din teza lui Rachel Player, sau estimatorul LWE.
Rețineți că aceasta este povestea pentru LWE. Ați folosit eticheta și pentru Ring LWE. Lucrurile sunt ceva mai complexe acolo și pot depinde de „comportamentul de divizare” al modulului $q$ în orice câmp numeric în care lucrați, deși sunt persoana greșită pentru a scrie un răspuns pe acest subiect.
