Aprenentatge amb errors

problema matemàtic que s'utilitza àmpliament per crear algorismes de xifratge segurs

En criptografia, l'aprenentatge amb errors (LWE) és un problema matemàtic que s'utilitza àmpliament per crear algorismes de xifratge segurs.[1] 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.[2] En termes més tècnics, es refereix al problema computacional d'inferir un lineal funció -ària sobre un anell finit de mostres donades alguns dels quals poden ser errònies. Es conjectura que el problema LWE és difícil de resoldre [1] i, per tant, és útil en criptografia.[3]

Més precisament, el problema LWE es defineix de la següent manera. Deixar denoten l'anell de nombres enters mòdul i deixar denoten el conjunt de -vectors superats . Existeix una determinada funció lineal desconeguda , i l'entrada al problema LWE és una mostra de parells , on i , de manera que amb alta probabilitat . A més, la desviació de la igualtat és segons algun model de soroll conegut. El problema requereix trobar la funció , 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.[4]

Definició

modifica

Denotar per   el grup additiu dels reals mòdul u. Deixar   ser un vector fix. Deixar   ser una distribució de probabilitat fixa sobre  . Denotar per   la distribució sobre   obtingut de la següent manera.

  1. Trieu un vector   de la distribució uniforme   ,
  2. Tria un número   de la distribució   ,
  3. Avaluar  , on   é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   cartografia   a   ), i l'addició final és a  .
  4. Sortida de la parella  .

El problema de l'aprenentatge amb errors   és trobar  , donat accés a moltes mostres a escollir polinomialment  .

Per cada  , denoteu amb   la gaussiana unidimensional amb mitjana i variància zero  , és a dir, la funció de densitat és   on  , i deixar   ser la distribució   obtingut tenint en compte   mòdul un. La versió de LWE considerada en la majoria dels resultats seria  

Referències

modifica
  1. 1,0 1,1 Regev, Oded Journal of the ACM, 56, 6, 2009, pàg. 1–40. arXiv: 2401.03703. DOI: 10.1145/1568318.1568324.
  2. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (en anglès) Journal of the ACM, 60, 6, November 2013, pàg. 1–35. DOI: 10.1145/2535925. ISSN: 0004-5411.
  3. «The Learning with Errors Problem» (en anglès). [Consulta: 2 maig 2024].
  4. Peikert, Chris. «Lattice Cryptography for the Internet». A: Mosca. Post-Quantum Cryptography (en anglès). 8772. Springer International Publishing, 2014-10-01, p. 197–219 (Lecture Notes in Computer Science). DOI 10.1007/978-3-319-11659-4_12. ISBN 978-3-319-11658-7.