Aprenentatge amb errors

En criptografia, l'aprenentatge amb errors (LWE) és un problema matemàtic que s'utilitza àmpliament per crear algorismes de xifratge segurs. Es basa en la idea de representar la informació secreta com un conjunt d'equacions amb errors. En altres paraules, LWE és una manera d'amagar el valor d'un secret introduint-hi soroll. En termes més tècnics, es refereix al problema computacional d'inferir un lineal $n$ funció -ària $f$ sobre un anell finit de mostres donades $y_{i}=f(\mathbf {x} _{i})$ alguns dels quals poden ser errònies. Es conjectura que el problema LWE és difícil de resoldre i, per tant, és útil en criptografia.

Més precisament, el problema LWE es defineix de la següent manera. Deixar $\mathbb {Z} _{q}$ denoten l'anell de nombres enters mòdul $q$ i deixar $\mathbb {Z} _{q}^{n}$ denoten el conjunt de $n$-vectors superats $\mathbb {Z} _{q}$. Existeix una determinada funció lineal desconeguda $f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}$, i l'entrada al problema LWE és una mostra de parells $(\mathbf {x} ,y)$, on $\mathbf {x} \in \mathbb {Z} _{q}^{n}$ i $y\in \mathbb {Z} _{q}$, de manera que amb alta probabilitat $y=f(\mathbf {x} )$. A més, la desviació de la igualtat és segons algun model de soroll conegut. El problema requereix trobar la funció $f$, o alguna aproximació propera, amb alta probabilitat.

El problema LWE va ser introduït per Oded Regev l'any 2005 (que va guanyar el premi Gödel 2018 per aquest treball); és una generalització del problema d'aprenentatge paritat. Regev va demostrar que el problema LWE és tan difícil de resoldre com diversos problemes de gelosia en el pitjor dels casos. Posteriorment, el problema LWE s'ha utilitzat com a suposició de duresa per crear sistemes criptogràfics de clau pública, com l'aprenentatge d'anell amb intercanvi de claus d'errors per Peikert.

Definició

Denotar per $\mathbb {T} =\mathbb {R} /\mathbb {Z}$ el grup additiu dels reals mòdul u. Deixar $\mathbf {s} \in \mathbb {Z} _{q}^{n}$ ser un vector fix. Deixar $\phi$ ser una distribució de probabilitat fixa sobre $\mathbb {T}$. Denotar per $A_{\mathbf {s} ,\phi }$ la distribució sobre $\mathbb {Z} _{q}^{n}\times \mathbb {T}$ obtingut de la següent manera.

1. Trieu un vector $\mathbf {a} \in \mathbb {Z} _{q}^{n}$ de la distribució uniforme $\mathbb {Z} _{q}^{n}$ ,
2. Tria un número $e\in \mathbb {T}$ de la distribució $\phi$ ,
3. Avaluar $t=\langle \mathbf {a} ,\mathbf {s} \rangle /q+e$, on $\textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\sum _{i=1}^{n}a_{i}s_{i}$ és el producte interior estàndard , la divisió es fa en el camp dels reals (o més formalment, aquesta "divisió per " és la notació per a l'homomorfisme del grup $\mathbb {Z} _{q}\longrightarrow \mathbb {T}$ cartografia $1\in \mathbb {Z} _{q}$ a $1/q+\mathbb {Z} \in \mathbb {T}$ ), i l'addició final és a $\mathbb {T}$.
4. Sortida de la parella $(\mathbf {a} ,t)$.

El problema de l'aprenentatge amb errors $\mathrm {LWE} _{q,\phi }$ és trobar $\mathbf {s} \in \mathbb {Z} _{q}^{n}$, donat accés a moltes mostres a escollir polinomialment $A_{\mathbf {s} ,\phi }$.

Per cada $\alpha >0$, denoteu amb $D_{\alpha }$ la gaussiana unidimensional amb mitjana i variància zero $\alpha ^{2}/(2\pi )$, és a dir, la funció de densitat és $D_{\alpha }(x)=\rho _{\alpha }(x)/\alpha$ on $\rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}$, i deixar $\Psi _{\alpha }$ ser la distribució $\mathbb {T}$ obtingut tenint en compte $D_{\alpha }$ mòdul un. La versió de LWE considerada en la majoria dels resultats seria $\mathrm {LWE} _{q,\Psi _{\alpha }}$