Entrenamiento basado en firmas con errores en el ring

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 22 de septiembre de 2021; las comprobaciones requieren 3 ediciones .

El aprendizaje en anillo con firma de errores es una de las clases de criptosistemas de clave pública basada en el problema del aprendizaje con errores en el anillo [ 1] , que reemplaza a los algoritmos de firma RSA y ECDSA utilizados . Durante la última década ha habido una investigación activa para crear algoritmos criptográficos que permanezcan seguros incluso si un atacante tiene los recursos de una computadora cuántica [2] [3] . La firma durante el entrenamiento con errores en el anillo es una de las poscuánticas [2] [3]firmas con la clave pública más pequeña y tamaños de firma. El uso del problema general de aprendizaje de errores en criptografía fue introducido por Oded Regev en 2005 y ha sido la fuente de varios desarrollos criptográficos [4] . Los fundadores de la criptografía de aprendizaje en anillo con errores (RLWE) creen que una característica de estos algoritmos basados en el aprendizaje con errores es la reducción demostrable de problemas complejos conocidos [1] [5] . Esta firma tiene una reducción comprobable al problema de encontrar el vector más corto en el campo de la criptografía en redes [6] . Esto significa que si se puede detectar un ataque al criptosistema RLWE, toda una clase de supuestos problemas computacionales complejos tendrán una solución [7] . La primera firma basada en RLWE fue desarrollada por Vadim Lyubashevsky [8] y refinada en 2011 [9] . Este artículo cubre los fundamentos matemáticos fundamentales de RLWE y se basa en un esquema llamado GLYPH [10] .

Antecedentes

Una firma digital es un medio para proteger la información y un medio para verificar la autenticidad de la fuente de información. La criptografía de clave pública proporciona un amplio conjunto de diferentes algoritmos criptográficos para crear firmas digitales. Sin embargo, las firmas de clave pública actualmente en uso se volverán completamente inseguras con el advenimiento de las computadoras cuánticas [2] [11] [12] Porque incluso una computadora cuántica relativamente pequeña capaz de procesar solo diez mil bits de información puede romper fácilmente todo utilizó algoritmos de cifrado de clave pública utilizados para proteger la privacidad y la firma digital en Internet [2] [13] . RSA , como uno de los algoritmos de clave pública más utilizados para la creación de firmas digitales , también se está volviendo vulnerable gracias a las computadoras cuánticas, ya que su seguridad se basa en la complejidad clásica de los problemas de factorización [14] . Y una computadora cuántica con aproximadamente 6n qubits de memoria y la capacidad de ejecutar el algoritmo de Shor puede factorizar fácilmente el producto de dos números primos de n bits, así como descifrar firmas digitales basadas en el logaritmo discreto y el logaritmo discreto de la curva elíptica. problemas [15] en un tiempo previsible [16 ] . Los requisitos previos para el surgimiento de tales computadoras ya están establecidos. Por ejemplo, el 20 de septiembre de 2019, el Financial Times informó: “Google afirma haber alcanzado la superioridad cuántica en una matriz de 54 qubits, de los cuales 53 eran funcionales y se usaban para realizar cálculos en 200 segundos, lo que llevaría alrededor de 10 000 años para una supercomputadora convencional.” [17] . Por lo tanto, una computadora cuántica relativamente pequeña, utilizando el algoritmo de Shor, puede descifrar rápidamente todas las firmas digitales utilizadas para garantizar la confidencialidad e integridad de la información en Internet hoy en día [16] .

Introducción

Las primitivas criptográficas basadas en problemas complejos de la teoría reticular juegan un papel clave en el campo de la investigación criptográfica poscuántica. En la ronda 2 de envíos de criptografía poscuántica, llamada NIST [18] , 12 de 26 se basan en redes y la mayoría de ellos se basan en el problema de aprendizaje con errores (LWE) y sus variantes. Se han propuesto una gran cantidad de primitivas criptográficas basadas en LWE, como el cifrado de clave pública, los protocolos de intercambio de claves, las firmas digitales, las familias de funciones pseudoaleatorias y otras [19] . Los protocolos criptográficos basados en el problema LWE son tan seguros como los protocolos basados en problemas de teoría de celosía , que hoy en día se consideran extremadamente complejos. Sin embargo, las primitivas criptográficas basadas en el problema LWE adolecen de tamaños de clave grandes, por lo que suelen ser ineficientes [19] . Esta deficiencia ha alentado a las personas a desarrollar variantes LWE más eficientes como Ring Learning con errores, RLWE) [1] . Se ha demostrado que el problema RLWE es tan difícil desde el punto de vista computacional como los problemas más difíciles de la teoría de celosías sobre clases especiales de celosías ideales [1] , y las aplicaciones criptográficas de RLWE suelen ser más eficientes que las LWE convencionales, especialmente en un módulo reducido de anillo polinomial ciclotómico. un polinomio, cuyo grado es la potencia de 2 [19] .

Problema RLWE

La firma RLWE funciona en un anillo de polinomio módulo un polinomio de grado con coeficientes en un campo finito para un primo impar . El conjunto de polinomios sobre un cuerpo finito con las operaciones de suma y multiplicación forma un anillo polinomial infinito [9] . La multiplicación y suma de polinomios funcionará como de costumbre con el módulo de resultado (es decir, anillo ). Un polinomio típico se expresa como: ${\ estilo de visualización \ Phi (x)}$ $norte$ ${\ Displaystyle Z_ {q}}$ $q$ $F_{q}[x]$ ${\ estilo de visualización \ 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}$

El campo tiene sus elementos en el conjunto . Si es una potencia de dos, entonces el polinomio será un polinomio circular . Son posibles otras opciones , pero los polinomios circulares correspondientes son más eficientes [9] . ${\ Displaystyle Z_ {q}}$ ${\ estilo de visualización \ {- (q-1)/2,...-1,0,1,... (q-1)/2\))$ $norte$ ${\ estilo de visualización \ Phi (x)}$ ${\ estilo de visualización x^{n}+1}$ $norte$

Hay dos formulaciones diferentes del problema de aprendizaje con errores en el anillo, la primera opción es " buscar ", la segunda opción es " solución " [1] .

Sea : el conjunto de polinomios aleatorios pero conocidos de con diferentes coeficientes para todos , el conjunto de pequeños polinomios aleatorios y desconocidos con respecto a la frontera en el anillo , y un polinomio pequeño desconocido con respecto a la frontera en el anillo , . ${\ estilo de visualización a_ {i} (x)}$ $Z_{q}[x]/\Phi(x)$ $F_q$ ${\ Displaystyle e_ {i} (x)}$ $b$ $Z_{q}[x]/\Phi(x)$ ${\ estilo de visualización s (x)}$ $b$ $Z_{q}[x]/\Phi(x)$ $b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$

Buscar : encuentra un polinomio de una lista de pares de polinomios ${\ estilo de visualización s (x)}$ ${\ estilo de visualización (a_ {i} (x), b_ {i} (x))}$

Decisión : esta lista de pares de polinomios determina si los polinomios se construyeron como o si se generaron aleatoriamente con coeficientes de todos . ${\ estilo de visualización (a_ {i} (x), b_ {i} (x))}$ ${\ Displaystyle b_ {i} (x)}$ $b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$ $Z_{q}[x]/\Phi(x)$ $F_q$

La complejidad de este problema radica en la elección de un polinomio factorial de grado , sobre el campo y la frontera . En muchos algoritmos basados en RLWE, la clave privada será un par de polinomios "pequeños" y . Entonces la clave pública que le corresponde será un par de polinomios , elegidos al azar , y un polinomio . Los datos y polinomios deben ser computacionalmente indecidibles para el problema de recuperación de polinomios [1] [6] . $\fi (x)$ $norte$ $F_q$ $b$ ${\ estilo de visualización s (x)}$ $ex)$ $hacha)$ $Z_{q}[x]/\Phi(x)$ $t(x)=(a(x)\cdot s(x))+e(x)$ $hacha)$ $t(x)$ ${\ estilo de visualización s (x)}$

Clase ciclotómica

Una clase ciclotómica sobre un campo generado por algún elemento es el conjunto de todos los elementos distintos que son las potencias [20] . ${\displaystyle \mathbb {F}_{q},\;q=p^{s))$ ${\displaystyle \alpha \in \mathbb {F} _{Q},\;Q=p^{S))$ ${\ estilo de visualización \ mathbb {F} _ {Q}}$ $q$ $\alfa$

Si es un elemento primitivo [21] (un elemento como para ) del campo , entonces la clase ciclotómica sobre el campo tendrá exactamente elementos. Cualquier elemento de una clase ciclotómica puede generar esta y solo esta clase y, en consecuencia, pertenecer solo a ella. $\alfa$ $\alpha^{Q-1}=1$ $\alpha^k\neq 1$ $0<k<Q-1$ ${\displaystyle \mathbb {F}_{Q},\;Q=q^{m))$ $C=\{\alfa,\;\alfa^q,\;\alfa^{q^2},\;\ldots,\;\alfa^{q^{m-1}}\}$ $\mathbb {F} _{q}$ $metro$

Ejemplo 1. Sea , y un elemento primitivo del campo , es decir , para . Considerando también que podemos obtener una descomposición de todos los elementos distintos de cero del campo en tres clases ciclotómicas sobre el campo : $q=2$ $Q=2^3=8$ $\alfa$ ${\ estilo de visualización \ mathbb {F} _ {8}}$ $\alpha^7=1$ $\alpha^i\neq 1$ $yo<7$ $\alpha^8=\alfa$ ${\ estilo de visualización \ mathbb {F} _ {8}}$ $\mathbb {F} _{2}$

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

Ejemplo 2. De manera similar, puede construir clases en el campo sobre el campo , es decir, . Sea un elemento primitivo del campo , por lo tanto . ${\ estilo de visualización \ mathbb {F} _ {16}}$ $\mathbb {F} _{4}$ $q=4,\;Q=q^2=16$ $\alfa$ ${\ estilo de visualización \ mathbb {F} _ {16}}$ $\alpha^{15}=1,\;\alpha^{16}=\alfa$

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

Generación de polinomios "pequeños"

La firma RLWE utiliza polinomios que se consideran "pequeños" con respecto a la norma uniforme . La norma uniforme para un polinomio es simplemente el valor absoluto más grande de los coeficientes del polinomio, y estos coeficientes se tratan como números enteros en , no en [6] El algoritmo de firma genera polinomios aleatorios cuya norma uniforme es pequeña con respecto a una determinada Perímetro. Esto se puede hacer fácilmente generando aleatoriamente todos los coeficientes del polinomio para garantizar, con una alta probabilidad, una norma menor o igual a este límite. Hay dos formas comunes de hacer esto [9] : $Z$ ${\ Displaystyle Z_ {q}}$ ${\displaystyle a_{0},...,a_{n-1))$

Uso de distribución uniforme : los coeficientes de un polinomio pequeño se eligen uniformemente de un conjunto de coeficientes. Sea un entero mucho menor que . Si seleccionamos al azar coeficientes polinómicos del conjunto , entonces la norma del polinomio será . $b$ $q$ ${\displaystyle \{-b,-b+1,-b+2,...-2,-1,0,1,2,...,b-2,b-1,b\))$ ${\ estilo de visualización \ leqslant b}$
Uso de muestreo gaussiano discreto : para un número entero impar , los coeficientes se seleccionan aleatoriamente mediante muestreo de un conjunto de acuerdo con una distribución gaussiana discreta con media y varianza . $q$ $\{-{\frac{q-1}{2}},...0,...{\frac {q-1}{2}}\}$ ${\ estilo de visualización 0}$ $\sigma^{2}$

En la firma RLWE GLYPH utilizada como ejemplo a continuación, se utilizará el método de distribución uniforme para los coeficientes de polinomios "pequeños" y el valor será mucho menor que [6] . $b$ $q$

Hashing de polinomios "pequeños"

La mayoría de los algoritmos de firma RLWE también requieren la capacidad de cifrar criptográficamente cadenas de bits arbitrarias en pequeños polinomios de acuerdo con alguna distribución [6] [10] . El siguiente ejemplo utiliza una función hash que toma una cadena de bits como entrada y genera un polinomio con coeficientes tales que exactamente uno de esos coeficientes tiene un valor absoluto mayor que cero y menor que un límite de número entero [10] . ${\mathsf {POLYHASH}}(\omega )$ $\omega$ $norte$ $k$ $b$

Muestreo de valores atípicos

Una característica clave de los algoritmos de firma RLWE es el uso de una técnica conocida como muestreo de varianza [9] [8] . En este método, si la norma uniforme del polinomio de la firma excede un límite fijo , ese polinomio se descartará y el proceso de generación de la firma comenzará de nuevo. Este proceso se repetirá hasta que la norma uniforme del polinomio sea menor o igual que la frontera. El muestreo de rechazo garantiza que la firma de salida no se pueda explotar utilizando los valores de la clave privada del firmante [10] . $\beta$

En este ejemplo, el límite será igual a , donde es el rango de muestreo uniforme y es el número de coeficientes distintos de cero asociados con el polinomio permitido [6] . $\beta$ ${\ estilo de visualización (bk)}$ $b$ $k$

Otros ejemplos

Según GLYPH [10] , el grado máximo de los polinomios será y por lo tanto tendrán coeficientes [6] .Los valores típicos para son 512 y 1024 [6] . Los coeficientes de estos polinomios serán elementos del campo , donde es un primo impar correspondiente a . Para , GLYPH define y es el número de coeficientes de salida distintos de cero iguales a [10] La seguridad del esquema de firma está estrechamente relacionada con los tamaños relativos de . $n-1$ $norte$ $norte$ $F_q$ $q$ $1{\bmod {4}}$ ${\ estilo de visualización n = 1024}$ ${\ estilo de visualización q = 59393, b = 16383}$ $k$ ${\mathsf {POLYHASH}}$ $dieciséis$ ${\ estilo de visualización n, q, b, k}$

Como se señaló anteriormente, el polinomio que define el anillo de polinomios utilizados será igual a . Finalmente, será un polinomio elegido aleatoriamente y fijo con coeficientes del conjunto . Todos los firmantes y verificadores sabrán y [10] . ${\ estilo de visualización \ Phi (x)}$ ${\ estilo de visualización x^{n}+1}$ $hacha)$ ${\ estilo de visualización \ {-b,...0,...,b\}}$ ${\ estilo de visualización n, q, b, k, \ Phi (x), a (x)}$ ${\ estilo de visualización \ beta = bk}$

Generación de clave pública

Según GLYPH [10] , la clave pública para firmar un mensaje se genera a través de los siguientes pasos: $METRO$

Generación de dos polinomios pequeños y con coeficientes elegidos aleatoriamente con distribución uniforme de un conjunto ${\ estilo de visualización s (x)}$ ${\ estilo de visualización e (x)}$ ${\ estilo de visualización \ {-b,...-1,0,1,...,b\))$
cálculo ${\ estilo de visualización t (x) = a (x) s (x) + e (x)}$
Distribución como clave pública de un objeto ${\ estilo de visualización t (x)}$

Los polinomios y sirven como clave privada y como clave pública correspondiente. La seguridad de este esquema de firma se basa en el siguiente problema: para un polinomio dado , es necesario encontrar polinomios pequeños y , tales que: . Si este problema es difícil de resolver, entonces el esquema de firma será difícil de falsificar. ${\ estilo de visualización s (x)}$ ${\ estilo de visualización e (x)}$ ${\ estilo de visualización t (x)}$ ${\ estilo de visualización t (x)}$ $f_1(x)$ ${\ estilo de visualización f_ {2} (x)}$ $a(x)f_{1}(x)+f_{2}(x)=t(x)$

Generación de firmas

Según GLYPH [10] , para firmar un mensaje expresado como una cadena de bits, se deben realizar las siguientes operaciones: $METRO$

Generación de dos polinomios pequeños y con coeficientes a partir de un conjunto ${\ estilo de visualización y_ {1} (x)}$ ${\ estilo de visualización y_ {2} (x)}$ ${\ estilo de visualización \ {-b,...-1,0,1,...,b\))$
cálculo $w(x)=a(x)y_{1}(x)+y_{2}(x)$
Mapeo a cadena de bits ${\ estilo de visualización w (x)}$ $\omega$
Cálculo (Este es un polinomio con k coeficientes distintos de cero. El símbolo "|" indica concatenación de cadenas) $c(x)={\mathsf {POLYHASH}}(\omega |M)$
cálculo $z_{1}(x)=s(x)c(x)+y_{1}(x)$
cálculo $z_{2}(x)=e(x)c(x)+y_{2}(x)$
Si y , repita los pasos 1-6 (Norma - norma uniforme ) ${\ estilo de visualización \|z_{1}(x)\|}$ $\|z_{2}(x)\|>\beta =(bk)$ $\|\cdot \|$
La firma es un triple de polinomios y ${\ estilo de visualización c (x), z_ {1} (x)}$ ${\ estilo de visualización z_ {2} (x)}$

Verificación de firma

Según GLYPH [10] , para verificar un mensaje expresado como una cadena de bits, se debe utilizar la clave pública del autor de este mensaje y una firma digital ( ): $METRO$ ${\ estilo de visualización t (x)}$ ${\ estilo de visualización c (x), z_ {1} (x), z_ {2} (x)}$

${\ estilo de visualización \|z_{1}(x)\|}$ , y , de lo contrario no se acepta la firma $\|z_{2}(x)\|\leqslant\beta$
cálculo $w'(x)=a(x)z_{1}(x)+z_{2}(x)-t(x)c(x)$
Mapeo a cadena de bits ${\ estilo de visualización w'(x)}$ ${\ estilo de visualización \ omega '}$
cálculo $c'(x)={\mathsf {POLYHASH}}(\omega '|M)$
Si , la firma es válida ${\ estilo de visualización c'(x)=c(x)}$

No es difícil mostrar la corrección del cheque:
$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)=$
${\ estilo de visualización = a (x) y_ {1} (x) + y_ {2} (x) = w (x)}$

Posibles ataques

En el trabajo de Luboshevsky [1] , se presta mucha atención a la seguridad del algoritmo, sin embargo, para resaltar estas propiedades del problema y demostrar su total cumplimiento con las declaradas, se deben realizar una serie de ataques directos a RLWE. llevado a cabo. El ataque está determinado por la elección de un campo numérico y un número primo , llamado módulo, junto con la distribución de errores. $k$ $q$

Dukas y Durmus propusieron una versión no dual de RLWE en una formulación ciclotómica y demostraron que la complejidad de la versión nueva y la antigua es idéntica [22] . Esta versión de RLWE genera la distribución de errores como una función gaussiana discreta en el anillo de enteros bajo incrustación canónica, en lugar de en la imagen ideal dual. Las versiones duales y no duales son equivalentes hasta la distribución de errores [23] . Para la versión no dual de RLWE, los autores de [24] propusieron un ataque a la versión “solución” de RLWE. El ataque usa un módulo de grado de residuo de 1, lo que da un homomorfismo de anillo → . El ataque funciona cuando, con una probabilidad abrumadora, la distribución de errores RLWE en un conjunto de pares toma valores solo en un pequeño subconjunto de . Luego, los autores de [24] dan toda una familia de ejemplos que son vulnerables a los ataques. Sin embargo, los campos numéricos vulnerables no son campos de Galois, por lo que el teorema de reducir la versión de "búsqueda" a la versión de "solución" no es aplicable y el ataque no puede usarse directamente para la variante de "búsqueda" del problema RLWE, que en realidad fue el objetivo del trabajo presentado [24] . $R$ $q$ ${\ estilo de visualización p: R}$ ${\ Displaystyle F_ {q}}$ ${\ estilo de texto p}$ ${\ Displaystyle F_ {q}}$

Sin embargo, posteriormente en otro trabajo [23] , este ataque se generalizó a algunos campos Galois y módulos de grado superior. También presentó su implementación para instancias específicas de RLWE, incluyendo la opción de reducir “ búsqueda ” a “ solución ”. Su principio fundamental era que el homomorfismo en el anillo se consideraba en la forma → (donde, es el grado de ) para , y que la distribución de errores difería de la aleatoria, utilizando una prueba estadística de chi-cuadrado en lugar de confiar en los valores del polinomio de error. Los autores también destacan que llevaron a cabo un ataque sobre una variación de RLWE con anillos ciclotómicos simples bajo ciertas suposiciones sobre el módulo y la tasa de error, que se realiza con éxito y con una alta probabilidad. Es decir, mostraron un ataque a la versión no dual de RLWE cuando el módulo es único y primo . Además, los autores del artículo llevaron a cabo otro ataque a la versión dual RLWE de la "solución" en el campo de ciclotomía -ésima con un módulo arbitrario , asumiendo que el ancho de la distribución de error es de aproximadamente . ${\ estilo de texto R}$ ${\ Displaystyle F_ {q}^{f}}$ $F$ $q$ ${\ estilo de visualización f> 1}$ ${\ estilo de texto p}$ $q$ $pags$ ${\ estilo de texto q}$ ${\ estilo de visualización 1/{\ sqrt {p))}$

Notas

↑ 1 2 3 4 5 6 7 Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded. Sobre redes ideales y aprendizaje con errores sobre anillos (inglés) // In Proc. De EUROCRYPT, Tomo 6110 de LNCS: revista. - 2010. - P. 1-23 .
↑ 1 2 3 4 Dahmen-Lhuissier, Sabine ETSI: criptografía cuántica segura . ETSI . Consultado el 5 de julio de 2015. Archivado desde el original el 21 de junio de 2015. (indefinido)
↑ 12 Introducción ._ _ pqcrypto.org . Fecha de acceso: 5 de julio de 2015. Archivado desde el original el 17 de julio de 2011. (indefinido)
↑ El problema del aprendizaje con errores . www.cims.nyu.edu . Consultado el 24 de mayo de 2015. Archivado desde el original el 23 de septiembre de 2015. (indefinido)
↑ ¿Qué significa el "cuento de advertencia" de GCHQ para la criptografía de celosía? . www.cc.gatech.edu . Fecha de acceso: 5 de julio de 2015. Archivado desde el original el 6 de julio de 2015. (indefinido)
↑ 1 2 3 4 5 6 7 8 Güneysu, Tim; Lyubashevsky, Vadim; Poppelman, Thomas. Criptografía práctica basada en entramado: un esquema exclusivo para sistemas integrados // Hardware criptográfico y sistemas integrados - CHES 2012 / Prouff, Emmanuel; Schaumont, Patrick. - Springer Berlín Heidelberg , 2012. - Vol. 7428.-Pág. 530-547. — (Apuntes de clase en informática). - ISBN 978-3-642-33026-1 . -doi : 10.1007 / 978-3-642-33027-8_31 .
↑ Micciancio, Daniele. El vector más corto en una red es difícil de aproximar dentro de alguna constante // In Proc. 39° Simposio de Fundamentos de Ciencias de la Computación: revista. - 1998. - Págs. 92-98 .
↑ 1 2 Lyubashevsky, Vadim. Fiat-Shamir con anulaciones: aplicaciones a firmas basadas en entramado y factorización // Avances en criptología - ASIACRYPT 2009 (sin especificar) / Matsui, Mitsuru. - Springer Berlín Heidelberg , 2009. - T. 5912. - S. 598-616. — (Apuntes de clase en informática). - ISBN 978-3-642-10365-0 . -doi : 10.1007 / 978-3-642-10366-7_35 .
↑ 1 2 3 4 5 Lyubashevsky, Vadim. Firmas de celosía sin trampillas (neopr.) . — 2011.
↑ 1 2 3 4 5 6 7 8 9 10 Chopra, Arjun GLYPH: una nueva instanciación del esquema de firma digital GLP . Archivo electrónico de la Asociación Internacional de Investigación Criptográfica (2017). Consultado el 26 de agosto de 2017. Archivado desde el original el 28 de agosto de 2017. (indefinido)
↑ Shah, Agam Reclamo de avance de computación cuántica de IBM . Consultado el 1 de junio de 2015. Archivado desde el original el 23 de septiembre de 2015. (indefinido)
↑ Markoff, John . Los investigadores informan sobre un hito en el desarrollo de una computadora cuántica (4 de marzo de 2015). Archivado desde el original el 26 de agosto de 2019. Consultado el 8 de noviembre de 2019.
↑ Beckman, David; Chari, Amalavoyal N.; Devabhaktuni, Srikrishna; Preskill, John. Redes eficientes para el factoraje cuántico (inglés) // Revisión física A : revista. - 1996. - vol. 54 , núm. 2 . - P. 1034-1063 . — ISSN 1050-2947 . -doi : 10.1103 / PhysRevA.54.1034 . - . — arXiv : quant-ph/9602016 .
↑ Bakhtiari, Maarof, 2012 , pág. 175.
↑ Shor P. Algorithms for Quantum Computation: Discrete Logarithms and Factoring // Foundations of Computer Science, Actas de 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, Alejandro. Simplificación excesiva de la factorización cuántica // Nature . - 2013. - 11 de julio ( vol. 499 , núm. 7457 ). - P. 163-165 . — ISSN 0028-0836 . -doi : 10.1038/ naturaleza12290 . — . -arXiv : 1301.7007 . _ — PMID 23846653 .
↑ Google afirma haber alcanzado la supremacía cuántica , The Financial Times (21 de septiembre de 2019). Archivado desde el original el 29 de abril de 2021. Consultado el 23 de octubre de 2019.
↑ Presentaciones de la Ronda 2 . Consultado el 21 de noviembre de 2019. Archivado desde el original el 14 de noviembre de 2019. (indefinido)
↑ 1 2 3 Wang, Yang; Wang, Mingqiang. Module-LWE versus Ring-LWE, Revisited (neopr.) . — 2019.
↑ Sagalovich, 2014 , pág. 105.
↑ Blahut, 1986 , pág. 99
↑ Ducas, L., Durmus, A. Ring-LWE en anillos polinómicos, Springer. - 2012. - S. 34-51 .
↑ 1 2 Hao Chen, Kristin Lauter, Katherine E. Stange. Ataques al problema Search-RLWE con pequeños errores . (enlace no disponible)
↑ 1 2 3 Yara Elias, Kristin E. Lauter, Ekin Ozman, Katherine E. Stange. Instancias probablemente débiles de Ring-LWE . Archivado desde el original el 8 de junio de 2019.

Literatura

Sagalovich Yu. L. Introducción a los códigos algebraicos . — Revista de Psicología General. - IPPI RAN, 2014. - 310 p.
Blahut R. E. Teoría y práctica de los códigos de control de errores . - Mir, 1986. - 576 p.
Bakhtiari M., Maarof MA Seria debilidad de seguridad en RSA Cryptosystem : [ ing. ] . - IJCSI, 2012. - 175 p.

Criptosistemas de clave pública

Algoritmos

Factorización de números enteros	criptosistema Benalo Bluma - Goldwasser Cayley sobrecargo Damgorda - Eureka GMR Goldwasser-Micali Nakasha - popa paga Rabín RSA Okamoto-Uchiyama Schmidt-Samoa
logaritmo discreto	BLS Cramer - Shoup Protocolo de Diffie-Hellman DSA ECDH Curva25519 X448 ECDSA EdDSA Ed25519 Ed448 ECMQV Intercambio de claves cifradas Esquema de ElGamal esquema de firma MQV esquema de Schnorr HABLA PVP STS
Criptografía en celosías	NTRUEncriptar NTRUSign Intercambio de claves basado en el aprendizaje con errores Entrenamiento basado en firmas con errores en el ring FELICIDAD Nueva Esperanza
Otro	AE CEILIDH EPOC Ecuaciones de campo ocultas IES la firma de lamport McEliece Criptosistema de mochila Merkle-Hellman Criptosistema de mochila Naccache-Stern Protocolo de tres pasos XTR

Teoría

Logaritmo discreto en una curva elíptica
Criptografía elíptica
Criptografía basada en hash
Criptografía no conmutativa
problema RSA
Función unidireccional con entrada secreta

Estándares

CRYPTREC
IEEE P1363
NESSIE
Paquete B de la NSA
Criptografía post cuántica

Temas

Firma electronica
OAEP
Huella dactilar
PKI
red de confianza
Tamaño de clave
Criptografía basada en identidad
Criptografía poscuántica
Tarjeta OpenPGP