De ce RLWE este mai ușor decât LWE și de ce putem alege $a_i$ ca o permutare a $a_1$ în RLWE, dar nu și LWE?

În LWE, avem

$$<a_1,s> + e + \mu_1\in \mathbb{Z}_q$$

pentru o cheie secretă $s\în \{0,1\}^n$ și $a_1\in \mathbb{Z}_q^n$

Aceasta este o criptare a unui număr $\mu_1$. Dacă vrem să criptăm $n$ diferit $\mu_i$, avem nevoie $n$ diferit $a_i$. Cu $n$ valorile $a_{11}, ..., a_{1n}$ am putut să criptăm un singur $\mu_1$.

Pentru RLWE, avem

$$a*s +e + m \in \mathbb{Z}_q[X]^n$$

pentru $a\in \mathbb{Z}_q[X]^n, e\in \mathbb{Z}_q[X]^n, m \in \mathbb{Z}_q[X]^n$, și $*$ este modul înmulțirii polinomului $x^n+1$. Aceasta este o criptare a unui polinom $m$ si astfel criptarea $n$ numere $m_1,...,m_n$. Cu $n$ valorile $a_1, ..., a_n$ am putut să criptăm $n$ numere.

Cred că asta a vrut să explice acest răspuns: https://crypto.stackexchange.com/a/47602. Pentru criptare $n$ valori în LWE, avem nevoie de un multiplu al mărimii cheii $n^2$ din cauza $a$lui. Pentru RLWE, avem nevoie doar $n$. Cu toate acestea, încă pentru RLWE, la pagina 5 din PDF pe care l-a legat, el spune că dacă vrem să criptăm $n$ vectori, putem alege pur și simplu $a_1\in \mathbb{Z}_q[X]^n$ si ceilalti $a_i$ ca funcţii de $a_1$ ca aceasta: $$\vec{a_i} = (a_i, ..., a_n, -a_1, ..., -a_{i-1}).$$ În primul rând, de ce se poate face acest lucru pentru RLWE, dar nu pentru LWE? Pentru LWE, avem un fel de sistem de ecuații liniare:

$$a_{i1}s_1 + a_{i2}s_2 + ... + a_{in}s_n + e_i = bi \mbox{ mod q}$$

asta se presupune a fi greu de rezolvat. Dacă o facem astfel încât $a_{i}$ este o permutare a $a_1$ atunci cred ca problema nu mai este grea. Am dreptate? Dar de ce este încă greu pentru RLWE? Oare doar pentru că pe RLWE nu avem un sistem de ecuații? Avem

$$a_i*s +e_i + m_i = b_i \mbox{ mod $x^n$ + 1}$$

pot fi $a_i$ fiind o permutare a $a_1$ Aici încă lasă problema grea, cred.

În primul rând, Regev descrie că RLWE poate fi privit ca o anumită instanță „structurată” a LWE. Asta pentru ca

1. puteți descrie polinoamele în termeni de vectori în $\mathbb{Z}_q^n$,
2. poti descrie plus de polinoame în termeni de plus de vectori în $\mathbb{Z}_q^n$, și
3. poti descrie multiplicare de polinoame $\bmod (x^n+1)$ în termeni de „produse scalare amuzante” ale vectorilor în $\mathbb{Z}_q^n$.

Ultimul pas este singurul cu adevărat non-trivial. Nu voi deriva totul aici, dar se poate arăta că $i$al-lea coeficient al produsului polinomial $a(x)b(x)\bmod (q, x^n+1)$ este de forma $\langle \vec b, \mathsf{negaciclic}^{\circ i}(\vec a)\rangle$, Unde $\mathsf{negaciclic}^{\circ i}(\vec a)$ este $i$-plierea operatiei care se deplaseaza circular $\vec a$ (la stânga sau la dreapta, uit mereu) și înmulțește coeficienții cu $-1$ când se „înfășoară”. Concret, este $i$-iterarea ori a operatiei

$$(a_0,\dots,a_{n-1})\mapsto (-a_{n-1},a_0,\dots,a_{n-2}).$$

Asta înseamnă că se poate exact descrieți o instanță RLWE $(a(x), a(x)s(x) + e(x))$ prin rescrierea lucrurilor în termeni de vectori întregi. În special, dacă setați $A$ să fie următoarea matrice (unde $[a,b,c]$ este o matrice cu coloane $a,b,c$)

$$A = [\mathsf{negaciclic}^{\circ 0}(\vec a),\mathsf{negaciclic}^{\circ 1}(\vec a),\dots, \mathsf{negaciclic}^{\ circ (n-1)}(\vec a)],$$

apoi instanța RLWE menționată mai sus exact corespunde instanței LWE $(A, As + e)$. După cum menționează Regev, asta $A$ nu mai este uniform aleatorie $\mathbb{Z}_q^{n\ori n}$, așa cum este în întregime specificat de $O(n)$ elemente.

În primul rând, de ce se poate face acest lucru pentru RLWE, dar nu pentru LWE?

Pentru a clarifica, ceea ce se face este considerând RLWE ca o formă structurată de LWE. Se schimbă unele ipoteze de structură în $A$ pentru unele economii în eficiență. Deoarece LWE este versiunea „nestructurată”, nu se poate presupune structura într-un obiect „nestructurat”.

Dacă o facem astfel încât $\vec a_i$ este o permutare a $\vec a_1$ atunci cred ca problema nu mai este grea.

Deoarece pur și simplu rescriem instanța noastră RLWE într-o altă limbă, versiunea „LWE structurată” este grea dacă versiunea RLWE este grea. Deci, RLWE poate fi privit ca spunând că (pentru permutări adecvate) aceasta este problema încă greu.

Rețineți că nu toate permutările funcționează. Acest lucru devine rapid tehnic, dar $\mathbb{Z}_q[x]/(x^n-1)$ a fost considerat inițial (de către Micciancio, pentru o variantă Ring a problemei SIS). Acest polinom nu este ireductibil (are rădăcină la $x = 1$). Există apoi un homomorfism (corespunzător evaluării polinoamelor la 1) care se mapează $a(x) \in\mathbb{Z}_q[x]/(x^n-1)\la \mathbb{Z}_q$, ceea ce duce la atacuri. Oricum, acest lucru este relevant pentru că înmulțirea este activată $\mathbb{Z}_q[x]/(x^n-1)$ corespunde ciclic permutări ale $\vec a$ (mai degrabă decât negaciclic cele descrise mai sus).

Toate acestea înseamnă că setul tuturor instanțelor RLWE poate fi văzut ca un subset al setului tuturor instanțelor LWE. Din această perspectivă, RLWE nu poate fi mai greu decât LWE --- orice algoritm care încalcă LWE rupe în mod egal RLWE. S-ar putea să se întrebe cât de ușor este „subsetul RLWE” --- există unele probleme cunoscute de rețea în care lucrurile devin mult mai ușor atunci când vă asumați structura (cred că SIVP este exemplul principal). Pentru problema RLWE, există în plus exemple în care dacă parametrizați greșit lucrurile devin mai ușoare, de exemplu atunci când utilizați $x^n-1$ un polinom ireductibil. Există, de asemenea, câteva atacuri cuantice non-triviale asupra unei variante apropiate a problemei SVP pentru instanțe RLWE (cred că este problema generatorului de principiu scurt).

Nimic din cele de mai sus nu implică (pentru polinoame precum $x^{2^k}+1$, care sunt utilizate în mod obișnuit) atacuri mai bune împotriva RLWE decât există pentru LWE. Există unii autori (și anume Bernstein) care cred că structura suplimentară ajută [1], dar nu s-a arătat încă nimic concret.

[1] El crede că ceva mai nuanțat legat de dimensiunea grupurilor Galois ale polinomului ales $f(x)$ folosit în RLWE. Polinomul $x^{2^k}+1$ are un grup mic Galois, de marime $O(\grad f)$. Mărimea grupului maxim de galois este $O((\grad f)!)$, mult mai mare. Grupuri mai mari de galois apar pentru polinoamele aleatoare w.h.p. și, prin urmare, sunt „mai puțin structurate”. Nu sunt cunoscute atacuri care să utilizeze micul grup Galois $x^{2^k}+1$.

„Putem pur și simplu alege $a_i \in \mathbb{Z}_q[X]^n$" => Cred că ar trebui să fie drept $\mathbb{Z}_q^n$.

Ceea ce trebuie să înțelegi din acest paragraf este faptul că criptarea

$\mu_0, \dots, \mu_{n-1}$ văzut ca un polinom $\mu = \sum \mu_i X^i$ cu RLWE și polinomul $\sum a_i X^i$, este echivalent cu criptarea fiecărei coordonate $\mu_j$ cu LWE și vectorul $\vec{a_j}=(a_{j}, a_{j+1}, \dots, a_{n-1}, -a_{1}, \dots, -a_{j-1})$.

De ce este adevărat? Pentru că dacă ne uităm la coeficientul de $X^j$ în $a*s +e + \mu \in \mathbb{Z}_q[X]^n$, obținem exact

$<a_j,s> + e_j + \mu_j$ (cu $e_j$ coeficientul de $X^j$ pentru polinom $e$).

Despre duritatea ipotezelor: RLWE este o presupunere distinctă (și mai ușoară) decât LWE. Securitatea sa a fost studiată independent. Despre presupunerea pe care o propui, dar eu doar remarc:

• Nu capturați RLWE (din cauza $-$).

• Pentru unele permutări, problema devine mult mai ușoară:

De exemplu, dacă $\sigma = (1,2)(3,4)\dots(n-1, n).$ (cu notația dvs. este $i_j = i_j + 1$ dacă $i_j$ este ciudat și $i_j -1$ dacă nu este).

Atunci noi avem $c_1= <a,s> + e_1 + \mu_1$, și $c_2 = \sum^{n/2}_{j=1} (a_{2j}s_{2j-1} + a_{2j-1}s_{2j}) + e_2 + \mu_2.$

Atunci $c_1 + c_2 = \sum^{n/2}_{j=1} (a_{2j}s_{2j-1} + a_{2j-1}s_{2j} + a_{2j}s_{2j} + a_{2j-1}s_{2j-1}) + e_1+ e_2 + \mu_1+ \mu_2.$

$=\sum^{n/2}_{j=1} (a_{2j} + a_{2j-1})(s_{2j-1} + s_{2j-1}) + e_1+ e_2 + (\ mu_1+ \mu_2).$

Apoi avem reducerea dimensiunii unui factor $2$.

Aș fi tentat să generalizez și să spun cu o permutare a ordinii $k$, puteți reduce dimensiunea unui factor $k$ (atunci probabil nu este sigur).