Lärande med fel

Inlärning med fel ( LWE ) är problemet med att hitta ett polynom med koefficienter från en viss restring för vilken ett system av linjära ekvationer ges som har fel (vilket gör ett enkelt beräkningsproblem svårt).

LWE introducerades [1] av Oded Regev 2005 och har visat sig vara ett anmärkningsvärt mångsidigt ramverk för kryptografiska konstruktioner, särskilt för post-kvantkryptografiska algoritmer [1] [2] .

En variant av inlärningsproblemet med fel, där polynom betraktas i faktorringen av polynom av ett visst polynom, kallas inlärning med fel i ringen .

Definition

Låt oss fixa parametern , modul och fördelningen av "fel" -sannolikheten på . Låta vara en sannolikhetsfördelning på , Erhålls genom att välja en vektor enhetligt slumpmässigt, välja ett fel i enlighet med och det resulterande uttrycket , där och addition utförs modulo . $n\geqslant 1$ $q\geqslant 2$ $\chi$ ${Z}_{q}$ $A_{\mathbf {s} ,\chi }$ $\mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}$ $\mathbf {a} \in \mathbb {Z} _{q}^{n}$ $\mathbf {e} \in \mathbb {Z} _{q}$ $\chi$ $(\mathbf {a} ,\langle \mathbf {a} ,\mathbf {s} \rangle +e)$ $\textstyle \langle \mathbf {a} ,\mathbf {s} \rangle =\summa _{i=1}^{n}a_{i}s_{i}$ $q$

Det sägs [3] att en algoritm löser problemet om för någon , med ett godtyckligt polynomantal av oberoende relationer från , den kommer att producera med hög sannolikhet . $\mathrm {LWE} _{q,\chi }$ $\mathbf {s} \in \mathbb {Z} _{q}^{n}$ $A_{\mathbf {s} ,\chi }$ $s$

Utseendehistorik

Uppkomsten av LWE-konceptet spåras i verk av Miklós Aitai och Cynthia Dwork [4] . De beskrev det första kryptosystemet med offentlig nyckel genom att använda gitterkryptografi , och dess efterföljande förbättringar och modifieringar [5] . LWE presenterades inte explicit i dessa papper, men en noggrann granskning av Aitai-Dwork-konstruktionen, förenklad i Regevs papper [6] , visar [3] att LWE-idéer implicit uppstår i detta papper.

Det är värt att notera att tidig forskning inom detta område [4] [6] förlitade sig på det otillräckligt välstuderade problemet med att hitta en unik kortaste vektor . Det var länge inte klart om det kunde ersättas av fler standardproblem på galler . Senare fick Chris Peikert [7] och Vadim Lyubashevsky tillsammans med Daniele Micchancio reda på [8] att problemet med att hitta en unik kortaste vektor faktiskt är motsvarigheten till det vanliga GapSVP-gitterproblemet , vilket ledde till en tydligare bild på detta område.

Problemexempel

Betrakta ett typiskt LWE-problem [3] : det är nödvändigt att återställa vektorn , som har en sekvens av ungefärliga linjära ekvationer i x. Till exempel: $x\in \mathbb {Z} _{q}^{n}$

{\begin{cases}14x_{1}+15x_{2}+5x_{3}+2x_{4}=8(mod17)\\13x_{1}+14x_{2}+14x_{3}+ 6x_{4}=16(mod17)\\\dots \\6x_{1}+7x_{2}+16x_{3}+2x_{4}=3(mod17),\\\end{cases}}

där varje relation är sann med ett litet ytterligare fel, säg ± , och vårt mål är att återhämta sig (i det här exemplet ). Utan fel skulle det vara lätt att hitta: till exempel i polynomtid , med den Gaussiska metoden . Att ta hänsyn till felet gör uppgiften mycket svårare, eftersom felet ökar med varje iteration och så småningom når okontrollerbara värden [3] . $ett$ $x$ $x=(0,13,9,11)$ $x$

Kryptografiska applikationer

Utbudet av kryptografiska tillämpningar för LWE har nyligen blivit ganska brett. Förutom kryptosystemexemplet nedan finns det mer effektiva system [2] [9] . Dessutom kan användningen av Ring-LWE göra systemet verkligen användbart [10] .

Det är särskilt värt att notera att LWE kan användas som grund för att skapa kryptografiska system som ger en helt homomorf kryptering . Till exempel användes det i implementeringen av det allmänt tillgängliga FHEW-biblioteket [11] .

Public key system

Betrakta ett enkelt exempel på ett kryptosystem med offentlig nyckel som föreslagits av Regev [1] . Det bygger på komplexiteten i att lösa LWE-problemet. Systemet beskrivs med följande siffror: -hemlig parameter, -dimension, -modul och sannolikhetsfördelning . För att säkerställa systemets säkerhet och korrekthet bör följande alternativ väljas: $n$ $m$ $q$ $\chi \in \mathbb {Z} _{q}$

$q\geq 2$ , ett primtal mellan och $n^{2}$ $2n^{2}$
$m=(1+\epsilon )(n+1)\log {q}$ för en godtycklig konstant $\epsilon$
$\alpha (n)=1/{\sqrt {n}}\log ^{2}{n}$

Då definieras kryptosystemet enligt följande:

Hemlig nyckel : Den hemliga nyckeln väljs godtyckligt. $\mathbf {s} \in \mathbb {Z} _{q}^{n}$
Offentlig nyckel : Låt oss välja vektorer godtyckligt och oberoende. Låt oss välja tillåtna fel oberoende i enlighet med fördelningen . Den publika nyckeln består av $m$ $a_{1},\ldots ,a_{m}\in \mathbb {Z} _{q}^{n}$ $e_{1},\ldots ,e_{m}\in \mathbb {Z} _{q}$ $\chi$ $(a_{i},b_{i}=\langle a_{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}$
Kryptering : Bitkryptering görs på följande sätt: en slumpmässig delmängd väljs från och chiffret bestäms som $x\in\{0,1\}$ $S$ $[m]$ $Enc(x)$ $(\summa _{i\in S}a_{i},x/2+\summa _{i\in S}b_{i})$
Dechiffrera : Dechiffrera detta om det är närmare än , och annars. $(a,b)$ $0$ $b-\langle a,\mathbf {s} \rangle /q$ $0$ ${\frac {1}{2))$ $ett$

I sina verk [1] [3] bevisade Oded Regev riktigheten och säkerheten hos detta kryptosystem med ett lämpligt val av parametrar.

Anteckningar

↑ 1 2 3 4 Oded Regev "On lattices, learning with errors, random linear codes, and cryptography", i Proceedings of the trettiosjunde årliga ACM-symposium om Theory of computing (Baltimore, MD, USA: ACM, 2005), 84 -93, http://portal.acm.org/citation.cfm?id=1060590.1060603 .
↑ 1 2 D. Micciancio och O. Regev. Gitterbaserad kryptografi. I DJ Bernstein och J. Buchmann, redaktörer, Post-quantum Cryprography. Springer, 2008
↑ 1 2 3 4 5 Oded Regev, "The Learning with Errors Problem" http://www.cims.nyu.edu/~regev/papers/lwesurvey.pdf Arkiverad 23 september 2015 på Wayback Machine
↑ 1 2 M. Ajtai och C. Dwork. Ett kryptosystem med offentlig nyckel med värsta/genomsnittliga likvärdighet. I Proc. 29:e årliga ACM Symp. på Theory of Computing (STOC), sidorna 284-293. 1997
↑ M. Ajtai och C. Dwork. De första och fjärde kryptosystemen med offentlig nyckel med värsta/genomsnittliga likvärdighet, 2007. Tillgänglig från ECCC på http://www.uni-trier.de/eccc/ (ej tillgänglig länk)
↑ 1 2 O. Regev. Nya gitterbaserade kryptografiska konstruktioner. Journal of the ACM, 51(6):899-942, 2004. Preliminär version i STOC'03
↑ C. Peikert. Public-key kryptosystem från det värsta fallet kortaste vektorproblem. I Proc. 41:a ACM Symp. om Theory of Computing (STOC), sidorna 333-342. 2009
↑ V. Lyubashevsky och D. Micciancio. Vid avkodning av avgränsat avstånd, unika kortaste vektorer och problemet med minsta avstånd. I CRYPTO, sidorna 577-594. 2009.
↑ C. Peikert, V. Vaikuntanathan och B. Waters. Ett ramverk för effektiv och komponerbar omedveten överföring. I CRYPTO, sidorna 554-571. 2008
↑ V. Lyubashevsky, C. Peikert och O. Regev. På idealiska galler och lärande med fel över ringar. I EUROCRYPT. 2010.
↑ Leo Ducas, Daniele Micciancio. FHEW: A Fully Homomorphic Encryption Library . Datum för åtkomst: 31 december 2014. Arkiverad från originalet den 21 maj 2016. (obestämd)

Litteratur

Postkvantkryptering (neopr.) . - Springer, 2008. - S. 245. - ISBN 978-3540887010 .
Peikert, Chris. Gitterkryptering för Internet (neopr.) / Mosca, Michele. - Springer International Publishing , 2014. - S. 197-219. — (Föreläsningsanteckningar i datavetenskap). — ISBN 978-3-319-11658-7 .
Chen, Yuanmi; Phong Q., Nguyen . BKZ 2.0 : Better Lattice Security Estimates . - Springer Berlin Heidelberg, 2011. - S. 1-20.