Antrenament bazat pe semnătură cu erori în ring

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 22 septembrie 2021; verificările necesită 3 modificări .

Învățarea în inel cu semnătură de erori este una dintre clasele de criptosisteme cu chei publice bazate pe problema învățării cu erori în inel [ 1] , care înlocuiește algoritmii de semnătură RSA și ECDSA utilizați . În ultimul deceniu au existat cercetări active pentru a crea algoritmi criptografici care rămân în siguranță chiar dacă un atacator are resursele unui computer cuantic [2] [3] . Semnătura de antrenament de eroare de inel este una dintre semnăturile post-cuantice [2] [3] cu cele mai mici dimensiuni de cheie publică și semnătură. Utilizarea problemei generale de învățare a erorilor în criptografie a fost introdusă de Oded Regev în 2005 și a fost sursa mai multor dezvoltări criptografice [4] . Fondatorii criptografiei ring learning with errors (RLWE) cred că o caracteristică a acestor algoritmi bazați pe învățarea cu erori este reducerea demonstrabilă a problemelor complexe cunoscute [1] [5] . Această semnătură are o reducere dovedibilă la problema găsirii celui mai scurt vector în domeniul criptografiei pe rețele [6] . Aceasta înseamnă că dacă un atac asupra criptosistemului RLWE poate fi detectat, atunci o întreagă clasă de presupuse probleme complexe de calcul va avea o soluție [7] . Prima semnătură bazată pe RLWE a fost dezvoltată de Vadim Lyubashevsky [8] și rafinată în 2011 [9] . Acest articol acoperă fundamentele matematice fundamentale ale RLWE și se bazează pe o schemă numită GLYPH [10] .

Fundal

O semnătură digitală este un mijloc de protejare a informațiilor și un mijloc de verificare a autenticității sursei de informații. Criptografia cu cheie publică oferă un set bogat de algoritmi criptografici diferiți pentru crearea semnăturilor digitale. Cu toate acestea, semnăturile cheii publice utilizate în prezent vor deveni complet nesigure odată cu apariția computerelor cuantice [2] [11] [12] Deoarece chiar și un computer cuantic relativ mic, capabil să proceseze doar zece mii de biți de informație, poate rupe cu ușurință toate pe scară largă. au folosit algoritmi de criptare cu chei publice utilizate pentru a proteja confidențialitatea și semnătura digitală pe Internet [2] [13] . RSA , ca unul dintre cei mai folosiți algoritmi de cheie publică pentru crearea semnăturilor digitale , devine vulnerabil și datorită calculatoarelor cuantice, deoarece securitatea sa se bazează pe complexitatea clasică a problemelor de factorizare [14] . Iar un computer cuantic cu aproximativ 6n qubiți de memorie și capacitatea de a executa algoritmul lui Shor poate factoriza cu ușurință produsul a două numere prime de n biți, precum și să spargă semnăturile digitale bazate pe logaritmul discret și logaritmul discret al curbei eliptice. probleme [15] într-un timp previzibil [16 ] . Condițiile preliminare pentru apariția unor astfel de computere sunt deja în vigoare. De exemplu, pe 20 septembrie 2019, Financial Times a raportat: „Google susține că a atins superioritatea cuantică pe o matrice de 54 de qubiți, dintre care 53 erau funcționali și folosiți pentru a efectua calcule în 200 de secunde, ceea ce ar dura aproximativ 10.000 de ani pentru un supercalculator convențional.” [17] . Astfel, un computer cuantic relativ mic, folosind algoritmul lui Shor, poate sparge rapid toate semnăturile digitale folosite pentru a asigura confidențialitatea și integritatea informațiilor de pe Internet astăzi [16] .

Introducere

Primitivele criptografice bazate pe probleme complexe din teoria rețelelor joacă un rol cheie în domeniul cercetării criptografice post-cuantice. În runda 2 a trimiterilor de criptografie post-cuantică, numită NIST [18] , 12 din 26 se bazează pe rețele și majoritatea se bazează pe problema Learning With Errors (LWE) și variantele acesteia. Au fost propuse un număr mare de primitive criptografice bazate pe LWE, cum ar fi criptarea cheii publice, protocoalele de schimb de chei, semnăturile digitale, familiile de funcții pseudo-aleatoare și altele [19] . Protocoalele criptografice bazate pe problema LWE sunt la fel de sigure ca și protocoalele bazate pe probleme de teoria rețelei , care astăzi sunt considerate extrem de complexe. Cu toate acestea, primitivele criptografice bazate pe problema LWE suferă de dimensiuni mari ale cheilor, prin urmare sunt de obicei ineficiente [19] .Acest neajuns i-a încurajat pe oameni să dezvolte variante LWE mai eficiente precum Ring Learning.cu erori, RLWE) [1] . S-a demonstrat că problema RLWE este la fel de dificilă din punct de vedere computațional ca și cele mai grele probleme din teoria rețelelor peste clase speciale de rețele ideale [1] , iar aplicațiile criptografice ale RLWE sunt de obicei mai eficiente decât LWE-urile convenționale, în special într-un inel polinomial ciclotomic redus modulo. un polinom, al cărui grad este puterea lui 2 [19] .

Problemă RLWE

Semnătura RLWE funcționează într-un inel polinomial modulo un polinom de grad cu coeficienți într-un câmp finit pentru un prim impar . Mulțimea de polinoame peste un câmp finit cu operațiile de adunare și înmulțire formează un inel polinom infinit [9] . Înmulțirea și adăugarea polinoamelor vor funcționa ca de obicei cu rezultatul modulo (adică inelul ). Un polinom tipic se exprimă astfel: $\Phi (x)$ $n$ $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}$

Câmpul are elementele sale în set . Dacă este o putere a lui doi, atunci polinomul va fi un polinom circular . Sunt posibile alte alegeri , dar polinoamele circulare corespunzătoare sunt mai eficiente [9] . $Z_{q)$ $\{-(q-1)/2,...-1,0,1,...(q-1)/2\)$ $n$ $\Phi (x)$ $x^{n}+1$ $n$

Există două formulări diferite ale problemei de învățare cu erori în inel, prima opțiune este „ căutare ”, a doua opțiune este „ soluție ” [1] .

Fie : să fie mulțimea de polinoame aleatoare, dar cunoscute de la cu coeficienți diferiți pentru toate , să fie mulțimea de polinoame mici aleatoare și necunoscute în raport cu granița din inel și să fie un mic polinom necunoscut în raport cu granița din inel , . $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)$

Căutare : găsiți un polinom dintr-o listă de perechi de polinoame $s(x)$ $(a_{i}(x), b_{i}(x))$

Decizie : Această listă de perechi de polinoame determină dacă polinoamele au fost construite ca sau au fost generate aleator din cu coeficienți din toate . $(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$

Complexitatea acestei probleme constă în alegerea unui polinom factor de grad , peste câmp și graniță . În mulți algoritmi bazați pe RLWE, cheia privată va fi o pereche de polinoame „mici” și . Atunci cheia publică corespunzătoare acesteia va fi o pereche de polinoame , alese aleatoriu dintre , și un polinom . Datele și polinoamele trebuie să fie indecidabile din punct de vedere computațional pentru problema de recuperare a polinomului [1] [6] . $\Phi (x)$ $n$ $F_q$ $b$ $s(x)$ $e(x)$ $topor)$ $Z_{q}[x]/\Phi (x)$ $t(x)=(a(x)\cdot s(x))+e(x)$ $topor)$ $t(x)$ $s(x)$

Clasa ciclotomică

O clasă ciclotomică peste un câmp generat de un element este mulțimea tuturor elementelor distincte care sunt puterile-leme [20] . $\mathbb {F} _{q},\;q=p^{s)$ $\alpha \in \mathbb {F} _{Q},\;Q=p^{S)$ $\mathbb {F} _{Q}$ $q$ $\alfa$

Dacă este un element primitiv [21] (un element ca pentru ) al câmpului , atunci clasa ciclotomică peste câmp va avea exact elemente. Orice element dintr-o clasă ciclotomică poate genera aceasta și numai această clasă și, în consecință, aparține numai acesteia. $\alfa$ $\alpha^{Q-1}=1$ $\alpha^k\neq 1$ $0<k<Q-1$ $\mathbb {F} _{Q},\;Q=q^{m)$ $C=\{\alpha,\;\alpha^q,\;\alpha^{q^2},\;\ldots,\;\alpha^{q^{m-1}}\}$ $\mathbb {F} _{q}$ $m$

Exemplul 1. Fie , și un element primitiv al câmpului , adică , pentru . Având în vedere, de asemenea , că putem obține o descompunere a tuturor elementelor nenule ale câmpului în trei clase ciclotomice pe câmp : $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{matrice}

Exemplul 2. În mod similar, puteți construi clase pe câmp peste câmpul , adică . Fie un element primitiv al câmpului , prin urmare . $\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{matrice}

Generarea de polinoame „mici”

Semnătura RLWE utilizează polinoame care sunt considerate „mici” în raport cu norma uniformă . Norma uniformă pentru un polinom este pur și simplu cea mai mare valoare absolută a coeficienților polinomului, iar acești coeficienți sunt tratați ca numere întregi în , nu în [6] .Algoritmul de semnătură generează polinoame aleatoare a căror normă uniformă este mică în raport cu un anumit limite. Acest lucru se poate realiza cu ușurință prin generarea aleatorie a tuturor coeficienților polinomului astfel încât să se garanteze, cu o probabilitate mare, o normă mai mică sau egală cu această limită. Există două moduri comune de a face acest lucru [9] : $Z$ $Z_{q)$ $a_{0},...,a_{n-1)$

Folosind distribuția uniformă : Coeficienții unui polinom mic sunt aleși uniform dintr-un set de coeficienți. Fie un număr întreg care este mult mai mic decât . Dacă selectăm aleatoriu coeficienți polinomi din mulțime , atunci norma polinoamului va fi . $b$ $q$ $\{-b,-b+1,-b+2,...-2,-1,0,1,2,...,b-2,b-1,b\)$ $\leqslant b$
Utilizarea eșantionării discrete gaussiene : Pentru un număr întreg impar , coeficienții sunt selectați aleatoriu prin eșantionare dintr-o mulțime conform unei distribuții gaussiene discrete cu medie și varianță . $q$ $\{-{\frac {q-1}{2}},...0,...{\frac {q-1}{2}}\}$ $0$ $\sigma ^{2}$

În semnătura RLWE GLYPH folosită ca exemplu mai jos, pentru coeficienții polinoamelor „mici” se va folosi metoda de distribuție uniformă , iar valoarea va fi mult mai mică decât [6] . $b$ $q$

Hashing polinoame „mici”

Majoritatea algoritmilor de semnătură RLWE necesită, de asemenea, capacitatea de a hashing criptografic șiruri de biți arbitrare în polinoame mici în conformitate cu o anumită distribuție [6] [10] . Exemplul de mai jos folosește o funcție hash care ia ca intrare un șir de biți și scoate un polinom cu coeficienți astfel încât exact unul dintre acești coeficienți să aibă o valoare absolută mai mare decât zero și mai mică decât un număr întreg [10] . ${\mathsf {POLYHASH}}(\omega )$ $\omega$ $n$ $k$ $b$

Eșantionare anormală

O caracteristică cheie a algoritmilor de semnătură RLWE este utilizarea unei tehnici cunoscute sub numele de eșantionare a varianței [9] [8] . În această metodă, dacă norma uniformă a polinomului semnăturii depășește o limită fixă , atunci polinomul respectiv va fi eliminat și procesul de generare a semnăturii va începe din nou. Acest proces se va repeta până când norma uniformă a polinomului este mai mică sau egală cu granița. Eșantionarea de respingere asigură că semnătura de ieșire nu poate fi exploatată folosind valorile cheii private ale semnatarului [10] . $\beta$

În acest exemplu, granița va fi egală cu , unde este intervalul de eșantionare uniformă și este numărul de coeficienți nenuli asociați cu polinomul permis [6] . $\beta$ $(bk)$ $b$ $k$

Alte exemple

Conform GLYPH [10] , gradul maxim de polinoame va fi și, prin urmare, va avea coeficienți [6] . Valorile tipice pentru sunt 512 și 1024 [6] . Coeficienții acestor polinoame vor fi elemente ale câmpului , unde este un prim impar corespunzător lui . Pentru , GLYPH definește și este numărul de coeficienți de ieșire non-zero egal cu [10] .Securitatea schemei de semnătură este strâns legată de dimensiunile relative ale . $n-1$ $n$ $n$ $F_q$ $q$ $1{\bmod {4}}$ $n=1024$ $q=59393,b=16383$ $k$ ${\mathsf {POLYHASH}}$ $16$ $n,q,b,k$

După cum sa menționat mai sus, polinomul care definește inelul de polinoame folosit va fi egal cu . În cele din urmă, va fi un polinom ales aleatoriu și fix cu coeficienți din mulțimea . Toți semnatarii și verificatorii vor ști și [10] . $\Phi (x)$ $x^{n}+1$ $topor)$ $\{-b,...0,...,b\)$ $n,q,b,k,\Phi(x),a(x)$ $\beta =bk$

Generarea cheii publice

Conform GLYPH [10] , cheia publică pentru semnarea unui mesaj este generată prin următorii pași: $M$

Generarea a două polinoame mici și cu coeficienți aleși aleatoriu cu o distribuție uniformă dintr-o mulțime $s(x)$ $e(x)$ $\{-b,...-1,0,1,...,b\)$
calcul $t(x)=a(x)s(x)+e(x)$
Distribuție ca cheie publică a unui obiect $t(x)$

Polinoamele și servesc ca cheie privată și ca cheie publică corespunzătoare. Securitatea acestei scheme de semnătură se bazează pe următoarea problemă: pentru un polinom dat , este necesar să se găsească polinoame mici și , astfel încât: . Dacă această problemă este dificil de rezolvat, atunci schema de semnătură va fi dificil de falsificat. $s(x)$ $e(x)$ $t(x)$ $t(x)$ $f_1(x)$ $f_{2}(x)$ $a(x)f_{1}(x)+f_{2}(x)=t(x)$

Generarea semnăturii

Conform GLYPH [10] , pentru a semna un mesaj exprimat ca șir de biți, trebuie efectuate următoarele operații: $M$

Generarea a două polinoame mici și cu coeficienți dintr-o mulțime $y_{1}(x)$ $y_{2}(x)$ $\{-b,...-1,0,1,...,b\)$
calcul $w(x)=a(x)y_{1}(x)+y_{2}(x)$
Maparea la șir de biți $w(x)$ $\omega$
Calcul (Acesta este un polinom cu k coeficienți non-zero. Simbolul „|” denotă concatenarea șirurilor) $c(x)={\mathsf {POLYHASH}}(\omega |M)$
calcul $z_{1}(x)=s(x)c(x)+y_{1}(x)$
calcul $z_{2}(x)=e(x)c(x)+y_{2}(x)$
Dacă și , atunci repetați pașii 1-6 (Normă - normă uniformă ) $\|z_{1}(x)\|$ $\|z_{2}(x)\|>\beta =(bk)$ $\|\cdot \|$
Semnătura este un triplu de polinoame și $c(x),z_{1}(x)$ $z_{2}(x)$

Verificarea semnăturii

Conform GLYPH [10] , pentru a verifica un mesaj exprimat ca șir de biți, trebuie să utilizați cheia publică a autorului acestui mesaj și o semnătură digitală ( ): $M$ $t(x)$ $c(x),z_{1}(x),z_{2}(x)$

$\|z_{1}(x)\|$ , și , în caz contrar, semnătura nu este acceptată $\|z_{2}(x)\|\leqslant \beta$
calcul $w'(x)=a(x)z_{1}(x)+z_{2}(x)-t(x)c(x)$
Maparea la șir de biți $w'(x)$ $\omega '$
calcul $c'(x)={\mathsf {POLYHASH}}(\omega '|M)$
Dacă , semnătura este valabilă $c'(x)=c(x)$

Nu este dificil să arăți corectitudinea verificării:
$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)$

Posibile atacuri

În lucrarea lui Luboshevsky [1] , se acordă multă atenție securității algoritmului, totuși, pentru a evidenția aceste proprietăți ale problemei și a dovedi conformitatea lor deplină cu cele declarate, ar trebui să fie o serie de atacuri directe asupra RLWE. efectuate. Atacul este determinat de alegerea unui câmp numeric și a unui număr prim , numit modul, împreună cu distribuția erorilor. $K$ $q$

Dukas și Durmus au propus o versiune non-duală a RLWE într-o formulare ciclotomică și au demonstrat că complexitatea versiunii noi și a celei vechi este identică [22] . Această versiune a RLWE generează distribuția erorii ca o funcție Gaussiană discretă în inelul de numere întregi sub încorporare canonică, mai degrabă decât în imaginea ideală duală. Versiunile duale și non-duale sunt echivalente până la distribuția erorilor [23] . Pentru versiunea nonduală a RLWE, autorii lui [24] au propus un atac asupra versiunii „soluție” a RLWE. Atacul folosește un modul de grad de reziduu de 1, care dă un homomorfism inel → . Atacul funcționează atunci când, cu o probabilitate copleșitoare, distribuția erorilor RLWE într-un set de perechi ia valori doar într-un mic subset de . Apoi, autorii lui [24] oferă o întreagă familie de exemple care sunt vulnerabile la atacuri. Cu toate acestea, câmpurile numerice vulnerabile nu sunt câmpuri Galois, așa că teorema reducerii versiunii „căutare” la versiunea „soluție” nu este aplicabilă și atacul nu poate fi utilizat direct pentru varianta „căutare” a problemei RLWE, care a fost de fapt. scopul lucrării prezentate [24] . $R$ $q$ $p:R$ $F_{q)$ ${\textstyle p}$ $F_{q)$

Totuși, mai târziu într-o altă lucrare [23] , acest atac a fost generalizat la un număr de câmpuri și module Galois de grad superior. De asemenea, a prezentat implementarea sa pentru anumite instanțe RLWE, inclusiv opțiunea de a reduce „ căutarea ” la „ soluție ”. Principiul său principal a fost că homomorfismul din inel a fost considerat sub forma → (unde, este gradul de ) pentru , și că distribuția erorilor diferă de aleatorie, folosind un test statistic chi-pătrat în loc să se bazeze pe valori a polinomului de eroare. Autorii subliniază, de asemenea, că au efectuat un atac asupra unei variații a RLWE cu inele ciclotomice simple sub anumite ipoteze despre modul și rata de eroare, care este realizat cu succes cu o mare probabilitate. Și anume, ei au arătat un atac asupra versiunii non-duale a RLWE atunci când modulul este unic și prim . În plus, autorii articolului au efectuat un alt atac asupra versiunii duale RLWE a „soluției” în câmpul de ciclotomie --lea cu un modul arbitrar , presupunând că lățimea distribuției erorilor este de aproximativ . ${\textstyle R}$ $F_{q}^{f)$ $f$ $q$ $f>1$ ${\textstyle p}$ $Q$ $p$ ${\textstyle q}$ $1/{\sqrt {p)}$

Note

↑ 1 2 3 4 5 6 7 Liubașevski, Vadim; Peikert, Chris; Regev, Oded. Pe zăbrele ideale și învățarea cu erori peste inele (engleză) // În Proc. Din EUROCRYPT, Volumul 6110 al LNCS: jurnal. - 2010. - P. 1-23 .
↑ 1 2 3 4 Dahmen-Lhuissier, Sabine ETSI - Quantum-Safe Cryptography . ETSI . Consultat la 5 iulie 2015. Arhivat din original la 21 iunie 2015. (nedefinit)
↑ 12 Introducere _ _ pqcrypto.org . Data accesului: 5 iulie 2015. Arhivat din original pe 17 iulie 2011. (nedefinit)
↑ Problema Învățare cu erori . www.cims.nyu.edu . Preluat la 24 mai 2015. Arhivat din original la 23 septembrie 2015. (nedefinit)
↑ Ce înseamnă „povestea de avertizare” a lui GCHQ pentru criptografia lattice? . www.cc.gatech.edu . Data accesului: 5 iulie 2015. Arhivat din original pe 6 iulie 2015. (nedefinit)
↑ 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 // Hardware criptografic și sisteme încorporate - CHES 2012 / Prouff, Emmanuel; Schaumont, Patrick. - Springer Berlin Heidelberg , 2012. - Vol. 7428.-P. 530-547. — (Note de curs în Informatică). - ISBN 978-3-642-33026-1 . - doi : 10.1007/978-3-642-33027-8_31 .
↑ Micciancio, Daniele. Cel mai scurt vector dintr-o rețea este greu de aproximat cu o constantă // În Proc. Al 39-lea simpozion despre fundamentele informaticii: jurnal. - 1998. - P. 92-98 .
↑ 1 2 Lyubashevsky, Vadim. Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures // Advances in Cryptology - ASIACRYPT 2009 (nespecificat) / Matsui, Mitsuru. - Springer Berlin Heidelberg , 2009. - T. 5912. - S. 598-616. — (Note de curs în Informatică). - ISBN 978-3-642-10365-0 . - doi : 10.1007/978-3-642-10366-7_35 .
↑ 1 2 3 4 5 Liubașevski, Vadim. Semnături de zăbrele fără trapă (neopr.) . — 2011.
↑ 1 2 3 4 5 6 7 8 9 10 Chopra, Arjun GLYPH: A New Instantiation of the GLP Digital Signature Scheme . Arhiva eprint Asociația Internațională de Cercetare Criptografică (2017). Preluat la 26 august 2017. Arhivat din original la 28 august 2017. (nedefinit)
↑ Shah, Agam revendicare revoluționară în domeniul calculului cuantic de la IBM . Consultat la 1 iunie 2015. Arhivat din original pe 23 septembrie 2015. (nedefinit)
↑ Markoff, John . Cercetătorii raportează un reper în dezvoltarea computerului cuantic (4 martie 2015). Arhivat din original pe 26 august 2019. Preluat la 8 noiembrie 2019.
↑ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John. Rețele eficiente pentru factoring cuantic (engleză) // Physical Review A : jurnal. - 1996. - Vol. 54 , nr. 2 . - P. 1034-1063 . — ISSN 1050-2947 . - doi : 10.1103/PhysRevA.54.1034 . - Cod . — arXiv : quant-ph/9602016 .
↑ Bakhtiari, Maarof, 2012 , p. 175.
↑ Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring // Foundations of Computer Science, 1994 Proceedings . , 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, Alexandru. Simplificarea excesivă a factoringului cuantic // Natura . - 2013. - 11 iulie ( vol. 499 , nr. 7457 ). - P. 163-165 . — ISSN 0028-0836 . - doi : 10.1038/nature12290 . — . - arXiv : 1301.7007 . — PMID 23846653 .
↑ Google pretinde că a atins supremația cuantică , The Financial Times (21 septembrie 2019). Arhivat din original pe 29 aprilie 2021. Preluat la 23 octombrie 2019.
↑ Runda 2 Trimiteri . Preluat la 21 noiembrie 2019. Arhivat din original la 14 noiembrie 2019. (nedefinit)
↑ 1 2 3 Wang, Yang; Wang, Mingqiang. Modul-LWE versus Ring-LWE, Revisited (neopr.) . — 2019.
↑ Sagalovici, 2014 , p. 105.
↑ Blahut, 1986 , p. 99.
↑ Ducas, L., Durmus, A. Ring-LWE în inele polinomiale, Springer. - 2012. - S. 34-51 .
↑ 1 2 Hao Chen, Kristin Lauter, Katherine E. Stange. Atacuri la problema Search-RLWE cu mici erori . (link indisponibil)
↑ 1 2 3 Yara Elias, Kristin E. Lauter, Ekin Ozman, Katherine E. Stange. Instanțe care se dovedesc slabe ale Ring-LWE . Arhivat din original pe 8 iunie 2019.

Literatură

Sagalovici Yu. L. Introducere în codurile algebrice . — Revista de psihologie generală. - IPPI RAN, 2014. - 310 p.
Blahut R. E. Teoria și practica codurilor de control al erorilor . - Mir, 1986. - 576 p.
Bakhtiari M., Maarof MA Slăbiciune gravă de securitate în Cryptosystem RSA : [ ing. ] . - IJCSI, 2012. - 175 p.

Criptosisteme cu cheie publică

Algoritmi

Factorizarea numerelor întregi	Criptosistemul Benalo Bluma - Goldwasser Cayley Purser Damgorda - Eureka GMR Goldwasser - Micali Nakasha - Pupa paye Rabin RSA Okamoto - Uchiyama Schmidt-Samoa
Logaritm discret	BLS Cramer - Shoup Protocolul Diffie-Hellman DSA ECDH Curba25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Schimb de chei criptate Schema lui ElGamal schema de semnătură MQV Schema Schnorr VORBIȚI SRP STS
Criptografia pe zăbrele	NTRUEncrypt NTRUSign Schimb de chei bazat pe învățare cu erori Antrenament bazat pe semnătură cu erori în ring FERICIRE Speranța nouă
Alte	AE CEILIDH EPOC Ecuații de câmp ascunse IES Semnătura lui Lampport McEliece Criptosistem de rucsac Merkle-Hellman Criptosistem de rucsac Naccache–Stern Protocol în trei etape XTR

Teorie

Logaritm discret pe o curbă eliptică
Criptografia eliptică
Criptografia bazată pe hash
Criptografia necomutativă
Problema RSA
Funcție unidirecțională cu intrare secretă

Standarde

CRYPTREC
IEEE P1363
NESSIE
NSA Suite B
Criptografie post cuantică

Subiecte

Semnatura electronica
OAEP
Amprenta
PKI
rețea de încredere
Dimensiunea cheii
Criptografia bazată pe identitate
Criptografia post-cuantică
Card OpenPGP