a lui Regev Sondaj LWE conţine o schiţă a dovezii.
Algoritmi. O modalitate naivă de a rezolva LWE este printr-un algoritm de probabilitate maximă. Presupuneți pentru simplitate că $q$ este polinom și că distribuția erorii este normală, ca mai sus. Apoi, nu este greu să demonstrezi că după aproximativ $O(n)$ ecuații, singura atribuire la $s$ că „satisface aproximativ” ecuațiile este cea corectă. Acest lucru poate fi demonstrat printr-un argument standard bazat pe legarea lui Chernoff și o unire legată peste toate $s\in\mathbb{Z}_q^n$. Acest lucru duce la un algoritm care utilizează numai $O(n)$ mostre și rulează în timp $2^{O(n \log n)}$. Ca corolar obținem că LWE este „bine definită” în sensul că cu mare probabilitate soluția $s$ este unic, presupunând că numărul de ecuații este $\Omega(n)$.
De asemenea, poate fi util să vizualizați LWE dintr-o perspectivă diferită --- și anume ca un interval de parametri pentru SIS unde este a priori neclar dacă o soluție ar trebui să existe sau nu, așa că cineva „plantează” una. Vedea aceste note pentru o anumită perspectivă pe aceste linii.
Rețineți că pentru SIS standard există multe soluții cu o probabilitate mare, așa că „LWE = SIS decizional (într-un interval de parametri)” este ușor de confundat dacă cineva nu este atent, vezi de exemplu această întrebare.
