Luați în considerare o formulare a LWE în care ni se oferă fie $(x,S x+e)$ sau $(x,u)$ --- Unde $S$ este o $m \times n$ matrice secretă/ascunsă, $x$ este un eșantionat aleatoriu $n \times 1$ vector, $e$ este o $m \times 1$ Vector de eroare gaussian și $u$ este un eșantion uniform aleatoriu --- și i s-a spus să facă distincția între aceste două cazuri. Acest lucru ar trebui să fie greu pentru algoritmii clasici, potrivit postării Aici. Numiți această problemă „LWE inversă”.
Am avut câteva întrebări despre setare.
Este problema distinctivă dificilă fără $e$?
Rețineți că în LWE standard, atunci când ni se dă $(A,A s+e)$ sau $(x,u)$, și a spus să distingă între cele două cazuri, problema este ușoară fără eroare. Rezolvăm doar un sistem de ecuații liniare pentru a obține $n$ intrări de $s$.
Totuși, aici trebuie să găsim $m \times n$ intrările din matricea noastră secretă $S$. Nu văd cum să fac asta cu doar $m$ ecuații.
Luați în considerare o variantă a problemei, unde ni se oferă fie $$ \{ (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_k, Sx_k + e_k)\} ~~\text{or}$$
$$\{ (x_1, u_1), (x_2, u_2), \ldots, (x_k, u_k)\},$$
și a spus să facă distincția între cele două cazuri. Numiți această problemă „LWE inversă cu un secret repetat”. $k$ este polinomial mare în $n$. Este grea aceasta problema?
Rețineți că un argument hibrid (cum ar fi cel folosit într-unul dintre răspunsuri Aici) indică faptul că problema rămâne grea. Aici este hibridul $H_i$:
$$H_i = \{ (x_1, Sx_1 + e_1), (x_2, Sx_2 + e_2), \ldots, (x_i, Sx_i + e_i), (x_{i+1}, u_{i+1}) \ldots , (x_{k}, u_{k}) \} .$$
Apoi, există o modalitate directă de a concluziona că dacă rezolvăm „LWE inversă cu un secret repetat”, putem rezolva LWE inversă. Deoarece LWE inversă este dificilă, problema noastră ar trebui să fie și ea grea.
Cu toate acestea, întâmpin dificultăți să-mi înțeleg acest fapt.
Rețineți că, dacă nu avem termenul de eroare, există o modalitate foarte ușoară de a distinge cele două cazuri, pt $k \geq n+1$. Rețineți că poate exista numai $n$ liniar independent $x_i$-s. Deci, diferența doar caută $n$ distinct $x_i$-s în mostrele date, notează unde matricea $S$ duce acești vectori către și pentru $n+1^{\text{th}}$ eșantion distinct, folosește liniaritatea pentru a calcula mai întâi unde $S$ îl duce la, apoi verifică dacă este în concordanță cu ceea ce a fost dat.
De ce termenii de eroare fac ca acest deosebitor să eșueze? Chiar și cu o eroare Gaussiană, din cauza dependenței liniare, nu ar trebui $n+1^{\text{th}}$ eșantionul distinct să fie suficient concentrat în jurul unei valori pentru ca diferența mea să reușească?
