Reducere LWE-search la SVP

Deci, pentru teza mea de diplomă, scriu despre criptosistemul LWE al lui Regev din lucrarea sa originală din 2005. Am terminat cu corectitudinea și securitatea (doar reducerea de la căutarea LWE prin reduceri de la mediu la cel mai rău și de la decizia de căutare, cu toate acestea, punctul principal al lucrării - reducerea GapSVP la căutarea LWE este în afara domeniului meu de aplicare lucru), dar acum aș dori să demonstrez un atac asupra unui astfel de sistem criptografic cu un atac asupra cheii publice. Aș dori să fac asta reducând căutarea LWE la SVP (sau CVP sau ceva similar) și apoi să folosesc un algoritm pentru rezolvarea SVP, de preferință ceva clasic precum LLL (chiar dacă nu sunt încă sigur dacă LLL este corect). alegere), deoarece mă duc pentru claritate și abundență de material pentru a studia din peste unele (teoretic) îmbunătățiri marginale a eficienței atacului. Ar putea cineva dintre voi să-mi îndrume către documentele potrivite pentru această reducere a LWE la SVP sau ceva despre care ați putea crede că ar fi relevant și potrivit pentru nivelul meu de maturitate și (in)experiență în domeniu. Mulțumesc anticipat.

Ați dat din greșeală pe un subiect deosebit de spinos/polarizant în criptografia bazată pe zăbrele, și anume ceea ce este cunoscut sub numele de etanşeitate a reducerii căutare-la-decizie.

Pe scurt, o declarație de formă

Orice algoritm $A$ împotriva problemei $A$ care curge în timp $T_A$ cu avantaj $\epsilon_A$ implică un algoritm $B$ împotriva problemei $B$ care curge în timp $T_B$ de avantaj $\epsilon_B$.

este o modalitate simplistă de a rezuma o reducere criptografică. În mod ideal, reducerea este strâmt, adică ambele:

1. $T_A\aproximativ T_B$ (cel mai bine este când $T_B = T_A$ plus niște mici cheltuieli generale pentru a rula reducerea) și
2. $\epsilon_A\aproximativ \epsilon_B$.

Există (aproximativ) două noțiuni de etanșeitate, asimptotic (unde sa zicem $T_B= O(T_A)$, și beton. Rețineți că o reducere cu timpul de rulare $T_A = 2^{512}T_B$ este strâns asimptotic, dar nu strâns concret.

Reducerea lui Regev este hotărât „concret nu strâns”. Este complicat din punct de vedere tehnic să specificăm exact ce înseamnă acest lucru, așa că voi face doar legătura cu literatura relativă.

1. O altă privire asupra etanșeității 2, care a adus inițial în discuție problemele de etanșeitate a reducerii (cred că în secțiunea 6 sau 7, dar nu îmi amintesc).

2. A Teza de masterat a pretins că oferă o reducere mai strânsă (și parametrizează un criptosistem bazat direct pe SVP, așa cum discutați), dar

3. (Un subset de) autorii primei lucrări au publicat un alt ziar luna aceasta, susținând că calculele tezei sunt greșite, iar reducerea este încă nestrânsă. Există și alte afirmații interesante aici --- Reducerea lui Regev este un algoritm BQP. Ei observă că nu este banal, în special algoritmul lui Shor (concret) este mult mai ușor de executat, ceea ce poate nu este grozav.

A mai fost câteva discuții despre grupul google NIST-PQC care ar putea fi de interes. Aproximativ, Dan Bernstein consideră că decalajul de etanșeitate este problematic. Chris Peikert a schițat o distincție între „etanșeitate avantajoasă” ($\epsilon_A\aproximativ \epsilon_B$) și „etanșeitatea timpului de rulare” ($T_A\aproximativ T_B$). Deși se pare că s-ar putea încerca să oficializeze această distincție, nu cunosc vreo scriere pe această temă în afara firului de e-mail legat.

Toate acestea înseamnă că mulți autori au sugerat că implicatii concrete a reducerii de la cel mai rău caz la mediu la SVP nu conduc la noțiuni semnificative de securitate, cu excepția cazului în care se alege incredibil parametri mari, care nu sunt utilizați în practică. „Cei mai mici parametri” pe care oamenii au reușit să-i obțină cu această strategie sunt încă mari (vezi teza de master), iar recent unii autori au susținut că acești parametri „mari, dar doar cu un factor 2x - 3x” sunt incorecți.

Deși toate aceste lucrări conțin descrieri ale reducerii LWE la SVP, nu sunt sigur dacă vreuna dintre acestea va fi deosebit de utilă din perspectivă expozitivă. Cu toate acestea, propunerea dvs. are cel mai mult sens în ipoteza că reducerea este strânsă --- din păcate nu este cazul (presupunând corectitudinea primei și a treia lucrări de mai sus, pe care nu le-am citit cu atenție), așa că propunerea dvs. poate fi mai mult dificil decât presupuneți.

Rețineți că existența unui decalaj de etanșeitate face nu înseamnă că LWE este nesigur, doar că (concret) baza securității LWE pe SVP nu este posibilă. Majoritatea susținătorilor criptografiei bazate pe zăbrele au procedat așadar după cum urmează:

1. folosiți existența reducerii de la cel mai rău caz la caz mediu pentru a argumenta calitativ că „distribuția LWE” nu este „defectuoasă din punct de vedere structural”. Ca exemplu de distribuție „structural defectuoasă” pentru o problemă, se știe că RSA este ușor dacă $N = pq$ este astfel încât $|p-q|$ este mic (via Algoritmul de factoring al lui Fermat). Acest lucru nu ar trebui să se întâmple cu adevărat dacă lucrurile sunt generate corect, dar linkul anterior a găsit niște chei generate incorect.

2. setați în mod concret parametrii bazați pe criptoanaliza directă a LWE, să spunem folosind Estimator LWE.

Dacă scopul tău principal este doar să ataci o instanță LWE, aș sugera să citești estimatorul LWE. Aproximativ, este folosit pentru parametrizarea instanțelor LWE. Face acest lucru prin estimarea costului (concret) al diferitelor atacuri cunoscute împotriva LWE. Probabil că este cel mai logic să te uiți la aceste atacuri cunoscute. Există o varietate de resurse bune privind atacurile cunoscute împotriva LWE, documentația estimatorului LWE este probabil cea mai actualizată.