Träning med fel i ringen

Ringinlärning med fel (RLWE) är ett beräkningsproblem som har formulerats som en variant av det mer allmänna inlärningsproblemet (LWE) för att dra fördel av ytterligare algebraisk struktur (d.v.s. polynomringar ) från gitterteorin [ 1] , som gjort det möjligt att öka och utöka krypteringsmöjligheterna för de kryptografiska applikationer som tidigare var baserade på LWE. RLWE-problemet har blivit grunden för nya kryptografiska algoritmer utformade för att skydda data från kryptoanalys av kvantdatorer , såväl som en viktig applikation för konstruktion av homomorfa krypteringsscheman . På grund av det faktum att den upplevda svårigheten att lösa RLWE-problemet är mycket hög även på en kvantdator, kan kryptografi baserad på den bli den grundläggande publika nyckelkryptografin i framtiden, precis som problemen med heltalsfaktorisering och diskret logaritm fungerade som grund för kryptografi med publik nyckel i början av 1980-talet [2] . Det bör noteras att RLWE kan approximeras av problemet att hitta den kortaste vektorn på ideala gitter , som är matematiskt strukturerade gitter som motsvarar ideal i en ring.

Bakgrund

Under det senaste decenniet har gitterkryptering fått mycket uppmärksamhet som grund för framtida kryptografi och har blivit ett snabbt växande område. Kryptografiska primitiver baserade på ovannämnda gitter är attraktiva genom att deras säkerhet ligger i den värsta beräkningskomplexiteten och sannolikt kommer att utgöra ett beräkningsproblem även för kvantdatorer.

För närvarande är säkerheten för modern kryptografi, i synnerhet kryptografi med offentliga nyckel, baserad på den förmodade olösligheten hos vissa teoretiska beräkningsproblem, såsom problemet med att faktorisera två valda heltal eller beräkna den diskreta logaritmen för att tillhandahålla digitala signaturer, nyckelutbyte och Integritet. Med tillräckligt stora nyckelstorlekar anses dessa kryptografiska system med offentliga nycklar praktiskt taget osårbara för hackning på moderna datorer, superdatorer eller speciella datorkluster. 1994 föreslog Peter Shor en kvantalgoritm [3] för den ovan nämnda faktoriseringen av heltal. Dess modifierade version kan lösa det diskreta logaritmproblemet i gruppen av elliptiska kurvpunkter (ECDLP). Algoritmen i sig kan inte användas på klassiska datorer, bara på kvantdatorer, för att lösa faktoriserings- eller diskret logaritmproblemet i polynomtid, och eftersom konceptet med kvantdatorer har börjat utvecklas snabbt för tillfället har det blivit oerhört viktigt att använda effektiva kvantalgoritmer med en offentlig krypteringsnyckel.

Beskrivning av algoritmen

Ring Error Learning (RLWE) är baserad på polynomaritmetik med koefficienter från finita fält [1] . Polynomet a(x) uttrycks enligt följande:

a(x) = a 0 + a 1 x + a 2 x 2 + … + a n-3 x n-3 + a n-2 x n-2 + a n-1 x n-1

För polynom definieras operationen av multiplikation och addition som för vanliga tal. I samband med RLWE-problemet kommer koefficienterna för polynom och alla operationer på dem att utföras i ett ändligt fält definierat som för ett primtal . Mängden polynom över ett ändligt fält med operationerna addition och multiplikation bildar en oändlig polynomring ( ), med en ändlig underring vars RLWE-problem fungerar. Vanligtvis är denna subring en kvotring som bildas av reduktionen av alla polynom i modulo ett irreducerbart polynom . Denna finita faktorring kan skrivas som . ${\textstil \mathbf {Z} /q\mathbf {Z} =\mathbf {F} _{q))$ ${\textstyle q}$ ${\textstyle \mathbf {F} _{q}[x]}$ ${\textstyle \mathbf {F} _{q}[x]}$ ${\textstil \Phi (x)}$ $\mathbf {F} _{q}[x]/\Phi (x)$

Om graden av polynomet är , då subringen blir en polynomring av grad mindre än modulo med koefficienter från . Värdena på , tillsammans med polynomet , definierar delvis det matematiska sammanhanget för RLWE-problemet. $\Phi (x)$ ${\textstyle n}$ $n$ $\Phi (x)$ $F_q$ ${\textstyle n}$ ${\textstyle q}$ $\Phi (x)$

Ett annat viktigt koncept för RLWE är begreppet "små" polynom med avseende på något mått. Det vanliga måttet för RLWE är den "oändliga" normen . Begreppet den oändliga normen för ett polynom introduceras helt enkelt som den största koefficienten för ett polynom när dessa koefficienter behandlas som heltal. Därför betyder det att den oändliga normen för polynomet är . Således är den största koefficienten . $||a(x)||_{\infty }=b$ $yxa)$ $b$ $b$ $yxa)$

Det sista viktiga konceptet för RLWE att förstå är genereringen av slumpmässiga polynom i och genereringen av "små" polynom. Ett slumpmässigt polynom genereras enkelt genom en enkel slumpmässig fördelning av polynomkoefficienterna från , där vanligtvis representeras som en mängd . $\mathbf {Z} _{q}[x]/\Phi (x)$ $n$ ${\displaystyle \mathbf {F} _{q))$ ${\displaystyle \mathbf {F} _{q))$ ${\displaystyle \{-(q-1)/2,...,-1,0,1,...,(q-1)/2\))$

Den slumpmässiga genereringen av "små" polynom görs genom att generera koefficienterna för polynomet som garanterar eller åtminstone gör det mycket troligt att dessa koefficienter kommer att vara små. Det finns två vanliga sätt att göra detta: ${\displaystyle \mathbf {F} _{q))$

Med användning av en diskret enhetlig fördelning - koefficienterna för ett litet polynom väljs enhetligt från en uppsättning små koefficienter. Låta vara ett heltal som är mycket mindre än . Om vi slumpmässigt väljer koefficienter från mängden kommer polynomet att vara "litet" med avseende på gränsvärdet ( ). ${\textstyle b}$ ${\textstyle q}$ ${\textstil \{-b,-b+1,-b+2,\ldots ,-2,-1,0,1,2,\ldots ,b-2,b-1,b\))$ ${\textstyle b}$
Med den Gaussiska funktionen - för ett udda värde väljs polynomets koefficienter slumpmässigt från mängden i enlighet med den diskreta Gaussfördelningen med matematisk förväntan och varians . Denna metod är mer komplicerad än den diskreta enhetliga fördelningen, men den låter dig bevisa säkerheten för algoritmen [4] . ${\textstyle q}$ ${\textstil \{-(q-1)/2,\ldots ,(q-1)/2\))$ $0$ ${\textstil \sigma }$

RLWE-problem

Formuleringen av inlärningsproblemet med fel i ringen kan ges på två olika sätt: det första alternativet är "sökning", det andra alternativet är "lösning". Båda i början av konstruktionen av algoritmen är desamma. Anta:

$a_{i}(x)$ - en uppsättning slumpmässiga men kända polynom från med olika koefficienter från alla . $\mathbf {Z} _{q}[x]/\Phi (x)$ ${\displaystyle \mathbf {F} _{q))$
$e_{i}(x)$ - en uppsättning små slumpmässiga och okända polynom med avseende på gränsen i ringen . $b$ $\mathbf {Z} _{q}[x]/\Phi (x)$
$s(x)$ är ett litet okänt polynom med avseende på gränsen i ringen . $b$ $\mathbf {Z} _{q}[x]/\Phi (x)$
$b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$ .

"Sök"-versionen av RLWE-problemet är att hitta ett polynom från en lista med polynompar . $s(x)$ $(a_{i}(x),b_{i}(x))$

"Lösningsversionen" av detta problem kan formuleras enligt följande: en given lista med polynompar avgör om polynomen konstruerades som eller genererades slumpmässigt från med koefficienter från alla . $(a_{i}(x),b_{i}(x))$ $b_{i}(x)$ $b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$ $\mathbf {Z} _{q}[x]/\Phi (x)$ ${\displaystyle \mathbf {F} _{q))$

Komplexiteten i detta problem ligger i valet av ett faktorpolynom , vars grad är över fältet och med litenhet associerad . I många algoritmer baserade på offentliga RLWE-nycklar kommer den privata nyckeln att vara ett par "små" polynom och . Då kommer den offentliga nyckeln som motsvarar den att vara ett par polynom , slumpmässigt utvalda från , och ett polynom . Data och polynom måste vara beräkningsmässigt obestämbara för polynomåterställningsproblemet . $\Phi (x)$ $n$ ${\displaystyle \mathbf {F} _{q))$ $b$ $s(x)$ $ex)$ $yxa)$ $\mathbf {Z} _{q}[x]/\Phi (x)$ $t(x)=(a(x)\cdot s(x))+e(x)$ $yxa)$ $t(x)$ $s(x)$

Säkerhet

I de fall där polynomet är cirkulärt är komplexiteten för att lösa RLWE-problemet i "sökversionen" ekvivalent med komplexiteten i att hitta en kort vektor (inte nödvändigtvis den kortaste) i ett idealiskt gitter som består av element representerade som heltalsvektorer [ 1] . Detta problem är allmänt känt som det ungefärliga kortaste vektorproblemet (α-ECV) och det består i att hitta en vektor som är α gånger kortare än den kortaste. α-ZKV-problemet i vanliga gitter är känt för att ha NP -komplexitet enligt Daniel Michancios arbete 2001, och detta beror inte på värdena av α som reducerar det till ett allmänt inlärningsproblem med fel [5] . Det finns dock fortfarande inget bevis som skulle visa att komplexiteten hos α-ZKV-problemet för ideala gitter är ekvivalent i genomsnitt med α-ZKV-problemet. Det finns dock bevis för att om något enskilt α-ZKV-problem är svårt att lösa på ideala gitter, så kommer RLWE-problemet att vara svårt att lösa i någon slumpmässig form. [ett] $\Phi (x)$ $\mathbf {Z} [x]/\Phi (x)$

Angående komplexiteten i problemet med att hitta den kortaste vektorn i ideala gitter, skriver forskaren Michael Schneider: "Framtills nu finns det ingen algoritm som använder den speciella strukturen hos ideala gitter. Det är allmänt ansett att lösa det kortaste vektorproblemet (och andra problem) i ideala galler är lika svårt som och i vanliga galler." [6] Det är bevisat att komplexiteten för dessa problem i vanliga gitter är NP. [5] . Det finns dock ett litet antal anhängare av en annan åsikt, som tror att ideala galler är lika säkra som vanliga. [7]

Peikert menar att denna likhet i säkerhet gör RLWE-problemet till en bra grund för framtida kryptografi. Han skriver: "Det finns ett matematiskt bevis på ' unikheten' (inom någon attackmodell) av ett sätt att bryta ett kryptosystem i dess slumpmässiga instanser - detta är förmågan att lösa motsvarande gitterproblem i värsta fall" [8]

Kryptografi RLWE

Den största fördelen med kryptografi baserad på inlärning med fel i ringen jämfört med originalet (på inlärning med fel från engelska LWE) är längden på de offentliga och privata nycklarna. För RLWE är det ungefär lika med kvadratroten av nyckellängden i LWE [1] . För en 128-bitars säkerhetsnivå kommer RLWE-algoritmen att använda en 7000-bitars publik nyckel. [9] Motsvarande LWE-schema är 49 miljoner bitar för samma säkerhetsnivå. [1] Å andra sidan är RLWE-nycklarna fortfarande längre än de som används av dess föregångare RSA och elliptiska Diffie-Hellman-kurvor. som kräver 3072 respektive 256 bitars nycklar för att nå 128-bitars säkerhetsnivå. Ur beräkningssynpunkt är RLWE-algoritmer åtminstone lika eller till och med bättre i prestanda än befintliga publika nyckelalgoritmer. [tio]

Det finns tre grupper av RLWE kryptografiska algoritmer:

Error Learning Key Exchange (RLWE-KEX)

Den grundläggande idén med att använda LWE och RLWE för nyckelutbyte föreslogs och uttrycktes 2011 av Jintai Ding vid University of Cincinnati. Grundtanken är att matrismultiplikation är associativ, och fel används för säkerhet. 2012 dyker en artikel [11] upp efter att ha lämnat in en patentansökan samma år.

2014 introducerade Peikert [12] ett nyckeltransportschema efter grundidén från Dean, som också använder en extra 1-bitars signal för avrundning i sin design. En RLWE-version av det klassiska MQV Diffie-Hellman nyckelutbytet publicerades senare av Zang [13] . Säkerheten för båda nyckelutbytesmetoderna är direkt relaterad till problemet med att hitta korta vektorer ungefär i ett idealiskt gitter.

Ring Error Training Signatur (RLWE-SIG)

RLWE-versionen av det klassiska Feig-Fiat-Shamir-protokollet skapades och signerades digitalt 2011 av Lyubashevsky. [14] Detaljerna i denna signatur avslöjades 2012 av Gunes, Lyubashevsky och Poppleman och publicerades i deras artikel "Practical Lattice-Based Cryptography - A Signature Scheme for Embedded Systems". [15] Dessa dokument lade grunden för många moderna algoritmer, av vilka några är baserade direkt på RLWE-problemet, och några av vilka inte alls är relaterade till RLWE. [16]

Homomorphic Encryption in Ring Error Learning (RLWE-HOM)

Målet med homomorf kryptering är att tillåta att känsliga data kan beräknas på datorenheter som inte bör betros med dessa data. Dessa enheter tillåts behandla chiffertexten vid utgången av homomorfisk kryptering. 2011 publicerade Brakerski och Vaikuntanathan "Full Homomorphic Encryption for Ring-LWE and Key-Dependent Message Security", som beskriver ett homomorfiskt krypteringsschema direkt för RLWE-problemet. [17]

Attacker mot RLWE

Det är mycket viktigt att förstå hur säker RLWE är som sådan. I Luboshevskys arbete [1] ägnas mycket uppmärksamhet åt algoritmens säkerhet, men för att belysa dessa egenskaper hos problemet och bevisa deras fulla överensstämmelse med de deklarerade, bör ett antal direkta attacker mot RLWE göras. utförd. Detta problem bestäms av valet av ett talfält och ett primtal som kallas modul, tillsammans med en felfördelning. Dukas och Durmus föreslog en icke-dubbel version av RLWE i en cyklotomisk miljö och bevisade att komplexiteten i den nya och den gamla versionen är identisk [18] . Denna version av RLWE genererar felfördelningen som en diskret Gaussisk funktion i ringen av heltal under kanonisk inbäddning, snarare än i den dubbla idealbilden. De dubbla och icke-dubbla varianterna är likvärdiga upp till felfördelningen [19] . För den icke-dubbla versionen av RLWE föreslog författarna till [20] en attack mot "lösningsversionen" av RLWE. Attacken använder en restgradsmodul på 1, vilket ger en ringhomomorfism → . Attacken fungerar när, med en överväldigande sannolikhet, fördelningen av RLWE-fel i en uppsättning par endast tar värden i en liten delmängd av . Sedan ger författarna till [20] en hel familj av exempel som är sårbara för attacker. Men sårbara numeriska fält är inte Galois-fält, så satsen att reducera "sök"-versionen till "lösning"-versionen är inte tillämplig och attacken kan inte direkt användas för "sök"-varianten av RLWE-problemet, som faktiskt var syftet med det presenterade arbetet [20] . ${\textstyle K}$ ${\textstyle q}$ ${\textstyle R}$ ${\textstyle q}$ ${\textstyle p:R}$ ${\textstyle \mathbf {F} _{q))$ ${\textstyle p}$ ${\textstyle \mathbf {F} _{q))$

Men senare i ett annat arbete [19] generaliserades denna attack till ett antal Galois-fält och moduler av högre grad. Den presenterade också dess implementering för specifika RLWE-instanser, inklusive möjligheten att reducera "sökning" till "lösning". Dess huvudprincip var att homomorfismen i ringen ansågs i formen → (där, är graden av ) för > 1, och att fördelningen av fel skilde sig från slumpmässigt, med hjälp av ett statistiskt chi-kvadrattest istället för att förlita sig på värden för felpolynomet. Författarna betonar också att de genomförde en attack på en variant av RLWE med enkla cyklotomiska ringar under vissa antaganden om modul och felfrekvens, vilket framgångsrikt utförs med hög sannolikhet. De visade nämligen en attack på den icke-dubbla versionen av RLWE när modulen är unik och prime . Dessutom genomförde artikelförfattarna ytterligare en attack på den dubbla RLWE-versionen av "lösningen" i det -: e cyklotomiska fältet med en godtycklig modul , förutsatt att bredden på felfördelningen är ca . ${\textstyle R}$ ${\textstyle \mathbf {F} _{q}^{f))$ ${\textstyle f}$ ${\textstyle q}$ ${\textstyle f}$ ${\textstyle p}$ ${\textstyle \mathbf {Q} }$ ${\textstyle p}$ ${\textstyle q}$ ${\textstyle 1/{\sqrt {p}}}$

Anteckningar

↑ 1 2 3 4 5 6 7 Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded. Om idealiska galler och lärande med fel över ringar . - 2012. Arkiverad den 26 november 2018.
↑ Peikert, Chris. Mosca, Michele. Gitterkryptering för Internet . - S. 197-219 . Arkiverad från originalet den 9 oktober 2018.
↑ P. Shor. Algoritmer för kvantberäkning : Diskreta logaritmer och faktorisering .
↑ Dwarakanath och Galbraith. Sampling från diskreta Gaussians för gitterbaserad kryptografi på en begränsad enhet // Tillämplig algebra inom teknik, kommunikation och beräkningar. - 2014. - 18 mars ( vol. 25 ). - S. 159-180 . — ISSN 3 . Arkiverad från originalet den 15 december 2018.
↑ 1 2 D. Micciancio. Den kortaste vektorn i ett gitter är svår att uppskatta inom någon konstant // SIAM Journal on Computing. - 2001. - 1 januari ( vol. 30 ). - S. 2008-2035 . — ISSN 0097-5397 . Arkiverad från originalet den 9 december 2016.
↑ Schneider, Michael. Siktning för kortaste vektorer i idealiska gitter : journal . — 2011.
↑ cr.yp.to: 2014.02.13: En subfield-logaritm attack mot ideala gitter . Hämtad 13 december 2018. Arkiverad från originalet 17 maj 2015. (obestämd)
↑ Vad betyder GCHQ:s "varnande berättelse" för gitterkryptografi? . www.eecs.umich.edu . Hämtad 5 januari 2016. Arkiverad från originalet 17 mars 2016. (obestämd)
↑ Singh, Vikram. Ett praktiskt nyckelutbyte för Internet med hjälp av Lattice Cryptography : journal . — 2015.
↑ Verbauwhede, Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid. Effektiv mjukvaruimplementering av Ring-LWE-kryptering (engelska) : tidskrift. — 2014.
↑ Ding, Jintai; Xie, Xiang; Lin, Xiaodong. Ett enkelt bevisligen säkert nyckelutbytessystem baserat på inlärning med fel Problem : journal . - 2012. - 1 januari.
↑ Peikert, Chris. Gitterkryptering för Internet (neopr.) . - 2014. - 1 januari.
↑ Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Snook, Michael; Dagdelen, Ozgur. Autentiserat nyckelutbyte från Ideal Lattices (engelska) : journal. — 2014.
↑ Lyubashevsky, Vadim. Gittersignaturer utan fälldörrar (neopr.) . — 2011.
↑ Güneysu, Tim; Lyubashevsky, Vadim; Poppelmann, Thomas. Praktisk gitterbaserad kryptografi: ett signaturschema för inbyggda system / Prouff, Emmanuel; Schaumont, Patrick. - Springer Berlin Heidelberg , 2012. - P. 530-547. — (Föreläsningsanteckningar i datavetenskap). - ISBN 978-3-642-33026-1 .
↑ BLISS Signature Scheme (nedlänk) . bliss.di.ens.fr . Hämtad 4 juli 2015. Arkiverad från originalet 6 oktober 2015. (obestämd)
↑ Brakerski, Zvika; Vaikuntanathan, Vinod. Fullständigt homomorf kryptering från Ring-LWE och säkerhet för nyckelberoende meddelanden (engelska) / Rogaway, Phillip. - Springer Berlin Heidelberg , 2011. - P. 505-524. — (Föreläsningsanteckningar i datavetenskap). — ISBN 978-3-642-22791-2 .
↑ Ducas, L., Durmus, A. Ring-LWE i polynomringar, Springer. - 2012. - S. 34-51 .
↑ 1 2 Hao Chen, Kristin Lauter, Katherine E. Stange. Attacker på Search-RLWE-problemet med små fel . Arkiverad från originalet den 15 december 2018.
↑ 1 2 3 Yara Elias, Kristin E. Lauter, Ekin Ozman, Katherine E. Stange. Bevisligen svaga instanser av Ring-LWE . Arkiverad från originalet den 8 juni 2019.