Mostra la font per a Aprenentatge amb errors

En [[criptografia]], '''l'aprenentatge amb errors''' ('''LWE''') és un problema matemàtic que s'utilitza àmpliament per crear [[Xifratge|algorismes de xifratge]] segurs.<ref name=":09">{{Ref-publicació|doi=10.1145/1568318.1568324|publicació=Journal of the ACM|volum=56|exemplar=6|pàgines=1–40|any=2009|cognom=Regev|nom=Oded|arxiv=2401.03703}}</ref> 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.<ref>{{Ref-publicació|cognom=Lyubashevsky|nom=Vadim|cognom2=Peikert|nom2=Chris|cognom3=Regev|nom3=Oded|data=November 2013|url=https://dl.acm.org/doi/10.1145/2535925|publicació=Journal of the ACM|llengua=en|volum=60|exemplar=6|pàgines=1–35|doi=10.1145/2535925|issn=0004-5411}}</ref> En termes més tècnics, es refereix al [[problema computacional]] d'inferir un lineal <math>n</math> funció -ària <math>f</math> sobre un [[Anell (matemàtiques)|anell]] finit de mostres donades <math>y_i = f(\mathbf{x}_i)</math> alguns dels quals poden ser errònies. Es conjectura que el problema LWE és difícil de resoldre <ref name=":09" /> i, per tant, és útil en criptografia.<ref>{{Ref-web|url=https://cims.nyu.edu/~regev/papers/lwesurvey.pdf|títol=The Learning with Errors Problem|consulta=2-5-2024|llengua=anglès}}</ref>

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

El problema LWE va ser introduït per [[Oded Regev (informàtic)|Oded Regev]] l'any 2005 (que va guanyar el [[premi Gödel]] 2018 per aquest treball); és una generalització del problema [[Aprenentatge paritat|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 la duresa computacional|suposició de duresa]] per crear [[Criptografia de clau pública|sistemes criptogràfics de clau pública]], com l'[[Aprenentatge en anell amb intercanvi de claus d'errors|aprenentatge d'anell amb intercanvi de claus d'errors]] per Peikert.<ref>{{Ref-llibre|editorial=Springer International Publishing|data=2014-10-01|isbn=978-3-319-11658-7|pàgines=197–219|col·lecció=Lecture Notes in Computer Science|nom=Chris|cognom=Peikert|editor=Mosca|doi=10.1007/978-3-319-11659-4_12|títol=Post-Quantum Cryptography|volum=8772|capítol=Lattice Cryptography for the Internet|llengua=anglès}}</ref>

== Definició ==
Denotar per <math>\mathbb{T}=\mathbb{R}/\mathbb{Z}</math> el [[Grup circular|grup additiu dels reals mòdul u]]. Deixar <math>\mathbf{s} \in \mathbb{Z}_q^n</math> ser un vector fix. Deixar <math>\phi</math> ser una distribució de probabilitat fixa sobre <math>\mathbb{T}</math>. Denotar per <math>A_{\mathbf{s},\phi}</math> la distribució sobre <math>\mathbb{Z}_q^n \times \mathbb{T}</math> obtingut de la següent manera.

# Trieu un vector <math>\mathbf{a}\in \mathbb{Z}_q^n</math> de la distribució uniforme <math>\mathbb{Z}_q^n</math> ,
# Tria un número <math>e\in\mathbb{T}</math> de la distribució <math>\phi</math> ,
# Avaluar <math>t=\langle \mathbf{a},\mathbf{s} \rangle /q + e</math>, on <math>\textstyle \langle \mathbf{a},\mathbf{s} \rangle = \sum_{i=1}^n a_i s_i</math> és el producte interior estàndard , la divisió es fa en el [[Nombre real|camp dels reals]] (o més formalment, aquesta "divisió per " és la notació per a l'homomorfisme del grup <math> \mathbb{Z}_q \longrightarrow \mathbb{T}</math> cartografia <math> 1 \in \mathbb{Z}_q </math> a <math> 1/q + \mathbb{Z} \in \mathbb{T}</math> ), i l'addició final és a <math>\mathbb{T}</math>.
# Sortida de la parella <math>(\mathbf{a},t)</math>.

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

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

== Referències ==
{{Referències}}

[[Categoria:Criptografia]]