Da, din motive generale.
Și anume, $a$ a fi inversabil este:
- Verificabil public și
- apare cu o probabilitate deloc neglijabilă $p$ (alegerea peste uniformă a $a$), vedea asta pentru detalii.
Ori de câte ori ai o condiție ca aceasta, poți avea orice adversar ipotetic să verifice mai întâi dacă condiția este valabilă și, dacă nu, atunci „ghiceste” răspunsul la întâmplare.
Acest lucru reduce avantajul printr-un factor multiplicativ $p$, dar deoarece acest lucru este deloc neglijabil, nu contează (pentru noțiunile asimptotice de securitate cel puțin).
Aceasta este tocmai explicația care este dată în lucrarea Steinfield și Stehle pe care ați legat-o, dar nu are nimic de-a face cu „problema de bază” cu care lucrează, fiind RLWE cu secrete uniforme și este valabilă în generalitatea pe care am menționat-o mai sus.
Independent de cele de mai sus, aceasta este de asemenea o motivație pentru reducerile de la cel mai rău caz la cel mai mic caz în cazul criptografiei latice.
Adesea, există un candidat „evident” pentru o problemă dificilă (factorizarea, de exemplu, sau BDD/CVP pentru zăbrele), dar stabilirea exactă a distribuției medii a cazurilor de utilizat poate fi neclară.
Reducerile de la cel mai rău caz la caz mediu arată că un număr de distribuții de cazuri medii pentru problemele LWE nu sunt „proaste din punct de vedere structural”, de exemplu:
- uniformă $a$, uniformă $s$, gaussian $e$ (de abatere standard $\geq \Omega(\sqrt{n})$, mai mare decât folosesc majoritatea oamenilor în practică)
- uniformă $a$, $s$ care urmează distribuţia de $e$
Odată ce știm uniforma aceea $a$ este distribuția „corectă” cu care să lucrăm, putem impune liber orice condiție „mare” (sensul apare cu o probabilitate neneglijabilă) pe care o dorim $a$, inclusiv faptul că este inversabil (sau are prima coordonată $1$, sau are $\sum_i a_i \equiv 0 \bmod q$ pentru polinomial-mare $q$, sau în esență orice). Rețineți că acest lucru este doar adevărat asimptotic totuși --- reducerile de la cel mai rău caz la mediu nu sunt deosebit de utile în parametrizarea concretă a LWE, deoarece se pot justifica parametrii mai mici prin criptoanalizarea directă a LWE.
