De ce RLWE este greu sau chiar are o soluție?

Mă gândeam de ce și cum problema RLWE este grea. Știu că este greu pentru că poate fi redusă la cea mai scurtă problemă vectorială, dar mă gândesc cum are o soluție.

Problema este practic:

$a_{i}(x)$ fi un set de polinoame aleatoare dar cunoscute din $F_q [ x ] / Φ ( x )$ cu coeficienți din toate $F_q$.

$e_i ( x ) $ să fie o mulțime de polinoame aleatoare mici și relativ necunoscute la o legătură $b$ în ring $F_q [ x ] / Φ ( x )$.

$s(x)$ fi un mic polinom necunoscut relativ la o limită $b$ în inel $F_q [ x ] / Φ ( x )$.

$b_i ( x ) = ( a_i ( x ) â s ( x ) ) + e_i ( x )$

Problema RLWE constă în găsirea polinomului $s$ dat $b$ și $a$. Dar de unde știu că am găsit-o, dacă eroarea $e$ ar putea fi orice? De exemplu, aș putea alege un moderat $s$ astfel încât rezultatul este aproape de $b$ și inventează orice $e$ astfel încât $b = a.s + e$. De cand $e$ este aleatoriu și necunoscut, ar putea fi orice. Nici măcar nu am o modalitate de a verifica că am găsit-o pe cea potrivită pentru că nu-l cunosc $e$.

Sunt două puncte cheie pe care le menționați (unul menționat de Poncho în comentarii --- repet aici în scop de expunere).

1. Erorile RLWE $e_i(x)$ sunt mic, și
2. secretul $s(x)$ este consistent pentru toate mostrele.

Aceasta oferă o modalitate destul de simplă de a verifica dacă ați recuperat corect $s(x)$ --- Împărțiți-vă setul de mostre în jumătate, recuperați-vă $s(x)$ din jumătate din probe și verificați că la fel $s(x)$ este astfel încât $a(x)s(x)\aprox b(x)$ (până la eroare „mică”) pe cealaltă jumătate a probelor. Pe toate probele ar trebui să verificați dacă s-a recuperat $e(x) = b(x)-a(x)s(x)$ este mic. Cred că această tehnică este cunoscută ca validare încrucișată în statistică, dar cum s-ar numi, funcționează bine și aici.

Mai este de subliniat că, în funcție de parametrii aleși, cu mare probabilitate veți avea ca secretul RLWE să fie el însuși unic (deci puteți dovedi că grijile dvs. nu pot apărea în primul rând, la parametrizarea corespunzătoare). Vezi de exemplu această întrebare pentru detalii.