Nu găsesc o expresie explicită pentru acest avantaj.
Nu există unul.
Acest lucru se datorează faptului că este în concordanță cu stadiul tehnicii teoriei complexității care $\mathsf{P} = \mathsf{NP}$, prin urmare $\mathsf{Adv}_{n,m,q,\sigma}^{\mathsf{DLWE}}$ este un polinom în dimensiunile parametrilor relevanți.
Este de asemenea în concordanță cu gândirea criptografică actuală că nu este cazul și că lucrurile mai agresive sunt adevărate, și anume că $\mathsf{Adv}^{\mathsf{DLWE}}_{n,m,q,\sigma}$ este aproape în întregime controlată de $n\log q$, și în special:
- $m$ poate fi destul de mare fără a afecta securitatea și
- $\sigma$ poate fi destul de mic (teoretic $\sigma = \Omega(\sqrt{n})$ este în general necesar, deși practic $\sigma = O(1) \aprox 8$ este comun).
Deci, cum se evaluează concret acest avantaj? În general, prin evaluarea (concretă) a stadiului actual al atacurilor cunoscute.
În acest scop, există două resurse principale:
„Estimatorul LWE” al lui Albrecth et al. este incredibil de popular. Puteți vedea lucrarea inițială Aici, și modulul (mai actualizat) sage Aici.
Propuneri concrete existente de primitive bazate pe zăbrele. De exemplu, finaliștii NIST PQC Kyber, Sabre și NTRUPrime includ toate analize (concrete) care își justifică alegerile parametrilor. Pentru primitivii mai grei, Standard de criptare homomorfă conține tabele cu parametrii sugerați, precum și rezumate ale atacurilor care au ghidat construcția acestor tabele.
Toate acestea fiind spuse...
Face reducerea $q$ si in crestere $\sigma$ implică un avantaj mai mic (și, prin urmare, o securitate mai bună?)
Toate celelalte fiind egale, răspunsul este da.
Având în vedere o instanță LWE $(\mathbf{A}, \vec b)$, se poate comuta modulul de la $q\mapsto q'$ (pentru $q' < q$, analiza este mai curată dacă $q' \mid q$ deşi).
Aceasta mapează aproximativ abaterea standard a erorii de la $\sigma \mapsto \frac{q'}{q}\sigma < \sigma$.
S-ar putea apoi crește această eroare la o abatere standard $\sigma' > \sigma > \frac{q'}{q}\sigma$ prin adăugarea unui Gaussian adecvat.
Aceasta înseamnă că există o reducere relativ simplă de la $\mathsf{DLWE}_{n, m, q, \sigma}\leq \mathsf{DLWE}_{n, m, q', \sigma'}$ pentru $\sigma' > \sigma$ și $q' \mid q$ (cazul lui $q' < q$ nu este mult mai greu, dar trebuie să faci față unor „erori de rotunjire”), așa că avantajul va fi mai mic.
