Signaturbaserad träning med fel i ringen

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 22 september 2021; kontroller kräver 3 redigeringar .

Ringinlärning med felsignatur är en av klasserna av kryptosystem med publik nyckel baserat på problemet med inlärning med fel i ringen [ 1] , som ersätter de använda RSA- och ECDSA- signaturalgoritmerna . Under det senaste decenniet har det gjorts aktiv forskning för att skapa kryptografiska algoritmer som förblir säkra även om en angripare har resurserna från en kvantdator [2] [3] . Ringfelsträningssignaturen är en av de post-quantum [2] [3] signaturerna med de minsta publika nyckel- och signaturstorlekarna. Användningen av det allmänna felinlärningsproblemet i kryptografi introducerades av Oded Regev 2005 och har varit källan till flera kryptografiska utvecklingar [4] . Grundarna av ring learning with errors (RLWE) kryptografi tror att en egenskap hos dessa algoritmer baserade på inlärning med fel är den bevisbara minskningen av kända komplexa problem [1] [5] . Denna signatur har en bevisbar minskning av problemet med att hitta den kortaste vektorn inom kryptografiområdet på gitter [6] . Detta betyder att om en attack på RLWE-krypteringssystemet kan upptäckas, kommer en hel klass av påstådda komplexa beräkningsproblem att ha en lösning [7] . Den första signaturen baserad på RLWE utvecklades av Vadim Lyubashevsky [8] och förfinades 2011 [9] . Den här artikeln täcker de grundläggande matematiska grunderna för RLWE och är baserad på ett schema som kallas GLYPH [10] .

Bakgrund

En digital signatur är ett sätt att skydda information och ett sätt att verifiera äktheten av informationskällan. Offentlig nyckelkryptering tillhandahåller en rik uppsättning olika kryptografiska algoritmer för att skapa digitala signaturer. Emellertid kommer de publika nyckelsignaturer som för närvarande används att bli helt osäkra med tillkomsten av kvantdatorer [2] [11] [12] Eftersom även en relativt liten kvantdator som kan bearbeta endast tiotusen bitar av information lätt kan bryta all omfattande använde krypteringsalgoritmer för offentliga nyckel som används för att skydda integritet och digital signatur på Internet [2] [13] . RSA , som en av de mest använda publika nyckelalgoritmerna för att skapa digitala signaturer , blir också sårbar tack vare kvantdatorer, eftersom dess säkerhet är baserad på den klassiska komplexiteten av faktoriseringsproblem [14] . Och en kvantdator med ungefär 6n qubits minne och förmågan att exekvera Shors algoritm kan enkelt faktorisera produkten av två n-bitars primtal, samt knäcka digitala signaturer baserade på den diskreta logaritmen och den diskreta logaritmen för den elliptiska kurvan problem [15] inom en överskådlig tid [16] . Förutsättningarna för uppkomsten av sådana datorer är redan på plats. Till exempel den 20 september 2019 rapporterade Financial Times: "Google påstår sig ha uppnått kvantöverlägsenhet på en uppsättning av 54 qubits, varav 53 var funktionella och användes för att utföra beräkningar på 200 sekunder, vilket skulle ta cirka 10 000 år för en konventionell superdator.” [17] . Således kan en relativt liten kvantdator, med hjälp av Shors algoritm, snabbt knäcka alla digitala signaturer som används för att säkerställa konfidentialitet och integritet för information på Internet idag [16] .

Inledning

Kryptografiska primitiver baserade på komplexa problem inom gitterteorin spelar en nyckelroll inom området för post-kvantkryptografisk forskning. I omgång 2 av postkvantkrypteringsinlämningar, kallade NIST [18] , är 12 av 26 baserade på gitter och de flesta av dem är baserade på Learning With Errors (LWE)-problemet och dess varianter. Ett stort antal LWE-baserade kryptografiska primitiver har föreslagits, såsom offentlig nyckelkryptering, nyckelutbytesprotokoll, digitala signaturer, familjer av pseudo-slumpmässiga funktioner och andra [19] . Kryptografiska protokoll baserade på LWE-problemet är lika säkra som protokoll baserade på lattice-teoretiska problem , som idag anses vara extremt komplexa. Kryptografiska primitiver baserade på LWE-problemet lider dock av stora nyckelstorlekar, därför är de vanligtvis ineffektiva [19] . Denna brist har uppmuntrat människor att utveckla mer effektiva LWE-varianter som Ring Learning. med fel, RLWE) [1] . Det har visat sig att RLWE-problemet är lika beräkningssvårt som de svåraste problemen inom gitterteorin över speciella klasser av ideala gitter [1] , och kryptografiska tillämpningar av RLWE är vanligtvis mer effektiva än konventionella LWE, särskilt i en cyklotomisk polynomring reducerad modulo ett polynom, vars grad är potensen 2 [19] .

RLWE-problem

RLWE-signaturen fungerar i en polynomring modulo ett gradpolynom med koefficienter i ett ändligt fält för ett udda primtal . Mängden polynom över ett ändligt fält med funktionerna addition och multiplikation bildar en oändlig polynomring [9] . Multiplikation och addition av polynom fungerar som vanligt med resultatet modulo (dvs ring ). Ett typiskt polynom uttrycks som: $\Phi (x)$ $n$ ${\displaystyle Z_{q))$ $q$ $F_{q}[x]$ $\Phi (x)$ $F_{q}[x]/\Phi (x)$

$a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-3}x^{n-3}+a_{n- 2}x^{n-2}+a_{n-1}x^{n-1}$

Fältet har sina element i uppsättningen . Om är en potens av två, så kommer polynomet att vara ett cirkulärt polynom . Andra val är möjliga , men motsvarande cirkulära polynom är mer effektiva [9] . ${\displaystyle Z_{q))$ ${\displaystyle \{-(q-1)/2,...-1,0,1,...(q-1)/2\))$ $n$ $\Phi (x)$ $x^{n}+1$ $n$

Det finns två olika formuleringar av inlärningsproblemet med fel i ringen, det första alternativet är " sök ", det andra alternativet är " lösning " [1] .

Låt : vara mängden slumpmässiga men kända polynom från med olika koefficienter för alla , vara mängden små slumpmässiga och okända polynom med avseende på gränsen i ringen , och vara ett litet okänt polynom med avseende på gränsen i ringen , . $a_{i}(x)$ $Z_{q}[x]/\Phi (x)$ $F_q$ $e_{i}(x)$ $b$ $Z_{q}[x]/\Phi (x)$ $s(x)$ $b$ $Z_{q}[x]/\Phi (x)$ $b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$

Sök : hitta ett polynom från en lista med polynompar $s(x)$ $(a_{i}(x),b_{i}(x))$

Beslut : Denna lista över polynompar avgör om polynomen byggdes 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)$ $Z_{q}[x]/\Phi (x)$ $F_q$

Komplexiteten i detta problem ligger i valet av ett faktorpolynom av grad , över fältet och gränsen . I många algoritmer baserade på RLWE 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 oavgörbara för polynomåterställningsproblemet [1] [6] . $\Phi (x)$ $n$ $F_q$ $b$ $s(x)$ $ex)$ $yxa)$ $Z_{q}[x]/\Phi (x)$ $t(x)=(a(x)\cdot s(x))+e(x)$ $yxa)$ $t(x)$ $s(x)$

Cyklotomisk klass

En cyklotomisk klass över ett fält som genereras av något element är uppsättningen av alla distinkta element som är th potenser [20] . ${\displaystyle \mathbb {F} _{q},\;q=p^{s))$ ${\displaystyle \alpha \in \mathbb {F} _{Q},\;Q=p^{S))$ $\mathbb {F} _{Q}$ $q$ $\alfa$

Om är ett primitivt element [21] (såsom ett element som för ) av fältet , då kommer den cyklotomiska klassen över fältet att ha exakt element. Vilket element som helst från en cyklotomisk klass kan generera denna och endast denna klass, och följaktligen bara tillhöra den. $\alfa$ $\alpha^{Q-1}=1$ $\alpha^k\neq 1$ $0<k<Q-1$ ${\displaystyle \mathbb {F} _{Q},\;Q=q^{m))$ $C=\{\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}\}$ $\mathbb {F} _{q}$ $m$

Exempel 1. Låt , och vara ett primitivt element i fältet , det vill säga för . Med tanke på det , kan vi erhålla en nedbrytning av alla element som inte är noll i fältet i tre cyklotomiska klasser över fältet : $q=2$ $Q=2^3=8$ $\alfa$ $\mathbb {F} _{8}$ $\alpha^7=1$ $\alpha^i\neq 1$ $i<7$ $\alpha^8=\alpha$ $\mathbb {F} _{8}$ $\mathbb {F} _{2}$

\begin{matrix} \{1\}, \\ \{\alpha,\;\alpha^2,\;\alpha^4\}, \\ \{\alpha^3,\;\alpha^6, \;\alpha^5\}. \end{matris}

Exempel 2. På samma sätt kan du bygga klasser på fältet över fältet , det vill säga . Låt vara en primitiv del av fältet , därför . $\mathbb {F} _{16}$ $\mathbb {F} _{4}$ $q=4,\;Q=q^2=16$ $\alfa$ $\mathbb {F} _{16}$ $\alpha^{15}=1,\;\alpha^{16}=\alpha$

\begin{matrix} \{1\}, \\ \{\alpha,\;\alpha^4\},\;\{\alpha^2,\;\alpha^8\}, \\ \{\ alpha^3,\;\alpha^{12}\},\;\{\alpha^5\},\;\{\alpha^{10}\}, \\ \{\alpha^6,\; \alpha^9\},\;\{\alpha^7,\;\alpha^{13}\}, \\ \{\alpha^{11},\;\alpha^{14}\}. \end{matris}

Generering av "små" polynom

RLWE-signaturen använder polynom som anses vara "små" med avseende på den enhetliga normen . Den enhetliga normen för ett polynom är helt enkelt det största absoluta värdet av koefficienterna för polynomet, och dessa koefficienter behandlas som heltal i , inte i [6] Signaturalgoritmen genererar slumpmässiga polynom vars enhetliga norm är liten med avseende på en viss gräns. Detta kan enkelt göras genom att slumpmässigt generera alla koefficienter för polynomet för att garantera, med hög sannolikhet, en norm som är mindre än eller lika med denna gräns. Det finns två vanliga sätt att göra detta [9] : $Z$ ${\displaystyle Z_{q))$ ${\displaystyle a_{0},...,a_{n-1))$

Använda enhetlig fördelning : Koefficienterna för ett litet polynom väljs enhetligt från en uppsättning koefficienter. Låta vara ett heltal som är mycket mindre än . Om vi slumpmässigt väljer polynomkoefficienter från mängden kommer normen för polynomet att vara . $b$ $q$ ${\displaystyle \{-b,-b+1,-b+2,...-2,-1,0,1,2,...,b-2,b-1,b\))$ $\leqslant b$
Använda diskret Gaussisk sampling : För ett udda heltal väljs koefficienterna slumpmässigt genom sampling från en uppsättning enligt en diskret Gaussisk fördelning med medelvärde och varians . $q$ $\{-{\frac {q-1}{2}},...0,...{\frac {q-1}{2}}\}$ $0$ $\sigma ^{2}$

I RLWE GLYPH-signaturen som används som ett exempel nedan kommer den enhetliga fördelningsmetoden att användas för koefficienterna för "små" polynom , och värdet kommer att vara mycket mindre än [6] . $b$ $q$

Hashing "små" polynom

De flesta RLWE-signaturalgoritmer kräver också förmågan att kryptografiskt hasha godtyckliga bitsträngar till små polynom enligt någon fördelning [6] [10] . Exemplet nedan använder en hashfunktion som tar en bitsträng som indata och matar ut ett polynom med koefficienter så att exakt en av dessa koefficienter har ett absolut värde som är större än noll och mindre än en heltalsgräns [10] . ${\mathsf {POLYHASH}}(\omega )$ $\omega$ $n$ $k$ $b$

Outlier sampling

En nyckelfunktion hos RLWE-signaturalgoritmer är användningen av en teknik som kallas varianssampling [9] [8] . I den här metoden, om den enhetliga normen för signaturpolynomet överskrider en fast gräns , kommer det polynomet att förkastas och signaturgenereringsprocessen kommer att starta om. Denna process kommer att upprepas tills den enhetliga normen för polynomet är mindre än eller lika med gränsen. Reject sampling säkerställer att utdatasignaturen inte kan utnyttjas med hjälp av signerarens privata nyckelvärden [10] . $\beta$

I det här exemplet kommer gränsen att vara lika med , där är intervallet för enhetlig sampling, och är antalet koefficienter som inte är noll associerade med det tillåtna polynomet [6] . $\beta$ $(bk)$ $b$ $k$

Andra exempel

Enligt GLYPH [10] kommer den maximala graden av polynom att vara och därför ha koefficienter [6] . Typiska värden för är 512 och 1024 [6] . Koefficienterna för dessa polynom kommer att vara element i fältet , där är ett udda primtal som motsvarar . För , GLYPH definierar och är antalet utgående koefficienter som inte är noll lika med [10] Säkerheten för signaturschemat är nära relaterad till de relativa storlekarna på . $n-1$ $n$ $n$ $F_q$ $q$ $1{\bmod {4}}$ $n=1024$ $q=59393,b=16383$ $k$ ${\mathsf {POLYHASH}}$ $16$ $n,q,b,k$

Som noterats ovan kommer polynomet som definierar ringen av använda polynom att vara lika med . Slutligen kommer ett slumpmässigt valt och fixerat polynom med koefficienter från mängden . Alla undertecknare och verifierare kommer att veta och [10] . $\Phi (x)$ $x^{n}+1$ $yxa)$ ${\displaystyle \{-b,...0,...,b\))$ $n,q,b,k,\Phi(x),a(x)$ $\beta =bk$

Public Key Generation

Enligt GLYPH [10] genereras den publika nyckeln för att signera ett meddelande genom följande steg: $M$

Generering av två små polynom och med koefficienter valda slumpmässigt med en enhetlig fördelning från en mängd $s(x)$ $e(x)$ ${\displaystyle \{-b,...-1,0,1,...,b\))$
beräkning $t(x)=a(x)s(x)+e(x)$
Distribution som ett objekts publika nyckel $t(x)$

Polynomen och fungerar som den privata nyckeln och som motsvarande offentliga nyckel. Säkerheten för detta signaturschema är baserat på följande problem: för ett givet polynom är det nödvändigt att hitta små polynom och , så att: . Om detta problem är svårt att lösa, kommer signaturschemat att vara svårt att förfalska. $s(x)$ $e(x)$ $t(x)$ $t(x)$ $f_1(x)$ $f_{2}(x)$ $a(x)f_{1}(x)+f_{2}(x)=t(x)$

Signaturgenerering

Enligt GLYPH [10] måste följande operationer utföras för att signera ett meddelande uttryckt som en bitsträng: $M$

Generering av två små polynom och med koefficienter från en mängd $y_{1}(x)$ $y_{2}(x)$ ${\displaystyle \{-b,...-1,0,1,...,b\))$
beräkning $w(x)=a(x)y_{1}(x)+y_{2}(x)$
Mappning till bitsträng $w(x)$ $\omega$
Beräkning (Detta är ett polynom med k koefficienter som inte är noll. Symbolen "|" anger strängsammansättning) $c(x)={\mathsf {POLYHASH}}(\omega |M)$
beräkning $z_{1}(x)=s(x)c(x)+y_{1}(x)$
beräkning $z_{2}(x)=e(x)c(x)+y_{2}(x)$
Om och , upprepa sedan steg 1-6 (Norm - enhetlig norm ) $\|z_{1}(x)\|$ $\|z_{2}(x)\|>\beta =(bk)$ $\|\cdot \|$
Signaturen är en trippel av polynom och $c(x),z_{1}(x)$ $z_{2}(x)$

Signaturverifiering

Enligt GLYPH [10] måste du för att verifiera ett meddelande uttryckt som en bitsträng använda den publika nyckeln för författaren av detta meddelande och en digital signatur ( ): $M$ $t(x)$ $c(x),z_{1}(x),z_{2}(x)$

$\|z_{1}(x)\|$ , och , annars accepteras inte signaturen $\|z_{2}(x)\|\leqslant \beta$
beräkning $w'(x)=a(x)z_{1}(x)+z_{2}(x)-t(x)c(x)$
Mappning till bitsträng $w'(x)$ $\omega '$
beräkning $c'(x)={\mathsf {POLYHASH}}(\omega '|M)$
Om , är signaturen giltig $c'(x)=c(x)$

Det är inte svårt att visa korrektheten av kontrollen:
$a(x)z_{1}(x)+z_{2}(x)-t(x)c(x)=a(x)[s(x)c(x)+y_{1} (x)]+z_{2}(x)-[a(x)s(x)+e(x)]c(x)=$
$=a(x)y_{1}(x)+z_{2}(x)-e(x)c(x)=a(x)y_{1}(x)+e(x)c (x)+y_{2}(x)-e(x)c(x)=$
$=a(x)y_{1}(x)+y_{2}(x)=w(x)$

Möjliga attacker

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. Attacken bestäms av valet av ett talfält och ett primtal , som kallas modulen, tillsammans med felfördelningen. $K$ $q$

Dukas och Durmus föreslog en icke-dubbel version av RLWE i en cyklotomisk formulering och bevisade att komplexiteten hos den nya och den gamla versionen är identisk [22] . 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 versionerna är likvärdiga upp till felfördelningen [23] . För den icke-dubbla versionen av RLWE föreslog författarna till [24] 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 [24] 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 om 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 [24] . $R$ $q$ $p:R$ ${\displaystyle F_{q))$ ${\textstyle p}$ ${\displaystyle F_{q))$

Men senare i ett annat arbete [23] 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 betraktades i formen → (där, är graden av ) för , 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ärdena av 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 cyklotomifältet med en godtycklig modul , förutsatt att bredden på felfördelningen är ca . ${\textstyle R}$ ${\displaystyle F_{q}^{f))$ $f$ $q$ $f>1$ ${\textstyle p}$ $F$ $sid$ ${\textstyle q}$ $1/{\sqrt {p))$

Anteckningar

↑ 1 2 3 4 5 6 7 Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded. På idealiska gitter och inlärning med fel över ringar (engelska) // In Proc. Av EUROCRYPT, volym 6110 av LNCS: tidskrift. - 2010. - S. 1-23 .
↑ 1 2 3 4 Dahmen-Lhuissier, Sabine ETSI - Quantum-Safe Cryptography . ETSI . Hämtad 5 juli 2015. Arkiverad från originalet 21 juni 2015. (obestämd)
↑ 12 Inledning _ _ pqcrypto.org . Datum för åtkomst: 5 juli 2015. Arkiverad från originalet 17 juli 2011. (obestämd)
↑ Problemet med att lära sig med fel . www.cims.nyu.edu . Hämtad 24 maj 2015. Arkiverad från originalet 23 september 2015. (obestämd)
↑ Vad betyder GCHQ:s "varnande berättelse" för gitterkryptografi? . www.cc.gatech.edu . Tillträdesdatum: 5 juli 2015. Arkiverad från originalet 6 juli 2015. (obestämd)
↑ 1 2 3 4 5 6 7 8 Güneysu, Tim; Lyubashevsky, Vadim; Poppelmann, Thomas. Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems // Kryptografisk hårdvara och inbyggda system - CHES 2012 / Prouff, Emmanuel; Schaumont, Patrick. - Springer Berlin Heidelberg , 2012. - Vol. 7428.-P. 530-547. — (Föreläsningsanteckningar i datavetenskap). - ISBN 978-3-642-33026-1 . - doi : 10.1007/978-3-642-33027-8_31 .
↑ Micciancio, Daniele. Den kortaste vektorn i ett gitter är svår att uppskatta inom någon konstant // In Proc. 39th Symposium on Foundations of Computer Science: tidskrift. - 1998. - S. 92-98 .
↑ 1 2 Lyubashevsky, Vadim. Fiat-Shamir med Aborts: Applications to Lattice and Factoring-Based Signatures // Advances in Cryptology - ASIACRYPT 2009 (ospecificerat) / Matsui, Mitsuru. - Springer Berlin Heidelberg , 2009. - T. 5912. - S. 598-616. — (Föreläsningsanteckningar i datavetenskap). - ISBN 978-3-642-10365-0 . - doi : 10.1007/978-3-642-10366-7_35 .
↑ 1 2 3 4 5 Lyubashevsky, Vadim. Gittersignaturer utan fälldörrar (neopr.) . — 2011.
↑ 1 2 3 4 5 6 7 8 9 10 Chopra, Arjun GLYPH: A New Instantiation of the GLP Digital Signature Scheme . International Association of Cryptographic Research eprint Archive (2017). Hämtad 26 augusti 2017. Arkiverad från originalet 28 augusti 2017. (obestämd)
↑ Shah, Agam Quantum computing genombrottsanspråk från IBM . Hämtad 1 juni 2015. Arkiverad från originalet 23 september 2015. (obestämd)
↑ Markoff, John . Forskare rapporterar Milestone in Developing Quantum Computer (4 mars 2015). Arkiverad från originalet den 26 augusti 2019. Hämtad 8 november 2019.
↑ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John. Efficient Networks for Quantum Factoring (engelska) // Physical Review A : journal. - 1996. - Vol. 54 , nr. 2 . - P. 1034-1063 . — ISSN 1050-2947 . - doi : 10.1103/PhysRevA.54.1034 . - . — arXiv : quant-ph/9602016 .
↑ Bakhtiari, Maarof, 2012 , sid. 175.
↑ Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring // Foundations of Computer Science, Proceedings 1994. , 35th Annual Symposium on - IEEE , 1994. - P. 124–134. - ISBN 0-8186-6580-7 - doi:10.1109/SFCS.1994.365700
↑ 1 2 Smolin, John A.; Smith, Graeme; Vargo, Alexander. Överförenkling av kvantfaktorering // Nature . - 2013. - 11 juli ( vol. 499 , nr 7457 ). - S. 163-165 . — ISSN 0028-0836 . - doi : 10.1038/nature12290 . — . - arXiv : 1301.7007 . — PMID 23846653 .
↑ Google påstår sig ha nått kvantöverhöghet , The Financial Times (21 september 2019). Arkiverad från originalet den 29 april 2021. Hämtad 23 oktober 2019.
↑ Inlämningar för omgång 2 . Hämtad 21 november 2019. Arkiverad från originalet 14 november 2019. (obestämd)
↑ 1 2 3 Wang, Yang; Wang, Mingqiang. Modul-LWE kontra Ring-LWE, Revisited (neopr.) . — 2019.
↑ Sagalovich, 2014 , sid. 105.
↑ Blahut, 1986 , sid. 99.
↑ 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 . (inte tillgänglig länk)
↑ 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.

Litteratur

Sagalovich Yu. L. Introduktion till algebraiska koder . — Genomgång av allmän psykologi. - IPPI RAN, 2014. - 310 sid.
Blahut R. E. Teori och praktik för felkontrollkoder . - Mir, 1986. - 576 sid.
Bakhtiari M., Maarof MA Allvarlig säkerhetssvaghet i RSA-kryptosystem : [ eng. ] . - IJCSI, 2012. - 175 sid.

Public key kryptosystem

Algoritmer

Faktorisering av heltal	Benalo kryptosystem Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Stern betalare Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Diskret logaritm	BLS Cramer - Shoup Diffie-Hellman-protokollet DSA ECDH Kurva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Krypterad nyckelutbyte Schema för ElGamal signaturschema MQV Schnorr-schema SPEKE SRP STS
Kryptografi på galler	NTRUEncrypt NTRUSign Inlärningsbaserat nyckelutbyte med fel Signaturbaserad träning med fel i ringen SALIGHET Nytt hopp
Övrig	AE CEILIDH EPOC Dolda fältekvationer IES Lamports signatur McEliece Merkle-Hellman ryggsäckskryptosystem Naccache–Stern ryggsäckskryptosystem Trestegsprotokoll XTR

Teori

Standarder

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Postkvantkryptering

Ämnen

Elektronisk signatur
OAEP
Fingeravtryck
PKI
nät av förtroende
Nyckelstorlek
Identitetsbaserad kryptografi
Postkvantkryptografi
OpenPGP-kort