LWE cu matricea A repetată

Luați în considerare următoarea versiune a Învățare cu erori.

Ești fie dat $(A, As_1 + e_1, As_2 + e_2, \ldots, As_k + e_k)$ sau $(A, u_1, u_2, \ldots, u_k)$, Unde

• $A$ este o $m \times n$ matrice ale cărei intrări provin din câmp $\mathbb{Z}_q$ --- intrările sunt eșantionate uniform la întâmplare.
• $u_1, u_2, \ldots, u_k$ sunt $m \times 1$, fiecare dintre ale căror intrări provin din teren $\mathbb{Z}_q$ uniform la întâmplare.
• Fiecare $e_1$, $e_2$, $\ldots$, $e_k$ este o $m \times 1$ Vector zgomot gaussian.
• Fiecare $s_1, s_2, \ldots, s_k$ este o $n \times 1$ șir secret.

Vi se spune să faceți distincția între aceste două cazuri.

Presupunând că LWE standard este greu, este și această problemă grea?

În general, o matrice diferită $A$ este prelevat pentru fiecare probă LWE. Aici, avem aceeași matrice $A$ dar $k$ diferite secrete.Schimbă asta ceva la setare?

Da, este încă greu printr-un simplu argument hibrid. În esență, pentru $i\în[k]$ definiți „distribuția mixtă”

$$H_i = (A, A\vec s_1 + \vec e_1,\dots, A\vec s_i + \vec e_i, \vec u_{i+1},\dots, \vec u_k).$$

Apoi, problema distingerii între $H_i$ și $H_{i+1}$ poate fi văzut a fi reductibilă la problema LWE. Când folosiți acest lucru pentru a analiza în mod concret lucrurile, acest lucru vă permite să limitați avantajul de a distinge între $H_0$ și $H_k$ de $k$ de ori avantajul unui distins LWE.

Acest argument (și mai general tehnica de reutilizare $A$) datează cel puțin de la Funcțiile trapei cu pierderi și aplicațiile lor de Peikert și Waters în 2008. Are câteva beneficii plauzibile ușoare, și anume:

1. s-ar putea standardiza în principiu o singură matrice $A$ pe care toți utilizatorii îl folosesc (similar cu modul în care au fost standardizate grupurile DDH) sau chiar
2. s-ar putea „reutiliza” o singură $A$ într-o perioadă de timp relativ scurtă, dar încă netrivială, să zicem 1 oră.

Totuși, în general, nu mai este atrăgător. Acest lucru este din două motive principale

1. se pot obține reduceri comparabile ale dimensiunii $A$ făcând apel la versiuni structurate ale LWE (îmbunătățind în același timp eficiența operațiunilor relevante) și
2. în practică nu se trimite des $A\in\mathbb{Z}_q^{n\ori m}$ cu preţul $nm\log_2q$ biți (care este mare, ceea ce duce la căutarea unor argumente de amortizare precum cel pe care îl propuneți). În schimb, puteți trimite pur și simplu o „sămânță” $\{0,1\}^\lambda$, care este extins într-o matrice aleatorie $A$ folosind o funcție de ieșire extensibilă la destinație. Majoritatea candidaților NIST PQC folosesc această abordare.

De asemenea, merită menționat că ideea de mai sus a unei „instanțe LWE standardizate” are câteva motive practice pentru care poate nu este inteligentă pe perioade lungi de timp, și anume

1. vă deschide la atacuri de precalculare (în mod similar cu alte standardizări ale grupului DDH, să spunem atacul LogJam) și, mai important,

2. se pot construi „instanțe LWE cu ușă în spate” --- aproximativ o distribuție de matrici aleatoare $A$ care nu se pot distinge din punct de vedere computațional de aleatorii, dar au o „trapă” care permite să spargă LWE.

Instanța LWE cu ușă în spate este relativ simplă (din păcate, nu îmi amintesc cui să o atribui). Reamintim că ipoteza NTRU generează chei o cheie publică $h$, și cheie secretă $f$, astfel încât $hf = g$ este mic". Folosind o formă adecvată de lucruri „matrice”, obținem matrici $H, F$ astfel încât:

• $HF = G$ este mic și
• $H$ nu se poate distinge din punct de vedere computațional de uniform aleatoriu.

Apoi, dacă folosim $H^t$ ca matrice aleatorie a unei instanțe LWE, de ex. ia o mostră $(H^t, H^t s + E)$, putem rupe cu ușurință ipoteza LWE folosind această matrice aleatorie, ca $F^t H^t s + F^t E = Gs + F^t E$ este „mic” (cred). Toate acestea sunt cu matricea $H$ fiind imposibil de distins din punct de vedere computațional de aleatoriu în NTRU, de ex. această ușă în spate a $H$ este greu de detectat.