Las firmas digitales son un medio para proteger la información digital de modificaciones intencionales y para autenticar la fuente de información digital. 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 claves públicas primarias actualmente en uso ( RSA y firmas de curvas elípticas) se volverán completamente inseguras si los científicos alguna vez pueden construir una computadora cuántica de tamaño moderado . [1] Post criptografía cuánticaes una clase de algoritmos criptográficos diseñados para ser resistentes al ataque de una criptografía cuántica. Se están creando varios algoritmos de firma digital postcuántica basados en problemas difíciles en las celosías que reemplazan las firmas de curva elíptica y RSA de uso común . Un subconjunto de estos esquemas basados en celosía se basa en un problema conocido como aprendizaje en anillo con errores . El aprendizaje en anillo con firmas digitales basadas en errores se encuentra entre las firmas postcuánticas con los tamaños de firma y clave pública más pequeños
Fondo
Los avances en la computación cuántica durante la última década y las perspectivas optimistas de las computadoras cuánticas reales dentro de 20 años han comenzado a amenazar la criptografía básica que protege Internet. [2] [3] Una computadora cuántica relativamente pequeña capaz de procesar solo diez mil bits de información fácilmente rompería todos los algoritmos de criptografía de clave pública ampliamente utilizados para proteger la privacidad y firmar digitalmente información en Internet. [1] [4]
Uno de los algoritmos de clave pública más utilizados para crear firmas digitales se conoce como RSA . Su seguridad se basa en la dificultad clásica de factorizar el producto de dos números primos grandes y desconocidos en los primos constituyentes. Se cree que el problema de la factorización de enteros es insoluble en cualquier computadora convencional si los números primos se eligen al azar y son lo suficientemente grandes. Sin embargo, para factorizar el producto de dos números primos de n bits, una computadora cuántica con aproximadamente 6n bits de memoria qubit lógica y capaz de ejecutar un programa conocido como algoritmo de Shor logrará fácilmente la tarea. [5] El algoritmo de Shor también puede romper rápidamente firmas digitales basándose en lo que se conoce como el problema de logaritmo discreto y el problema de logaritmo discreto de curva elíptica más esotérico . En efecto, una computadora cuántica relativamente pequeña que ejecute el algoritmo de Shor podría romper rápidamente todas las firmas digitales utilizadas para garantizar la privacidad e integridad de la información en Internet en la actualidad.
Aunque no sabemos cuándo existirá una computadora cuántica para romper RSA y otros algoritmos de firma digital, ha habido una investigación activa durante la última década para crear algoritmos criptográficos que permanezcan seguros incluso cuando un atacante tiene los recursos de una computadora cuántica a su alcance. disposición. [1] [6] Esta nueva área de la criptografía se llama criptografía Post Quantum o Quantum Safe . [1] [6] Este artículo trata sobre una clase de estos algoritmos: firmas digitales basadas en el problema de Aprendizaje en anillo con errores. El uso del problema general de aprendizaje con errores en criptografía fue introducido por Oded Regev en 2005 y ha sido la fuente de varios diseños criptográficos. [7]
Los creadores de la base de Aprendizaje con errores basado en anillo (RLWE) para la criptografía creen que una característica importante de estos algoritmos basados en Aprendizaje en anillo con errores es su reducción demostrable a problemas difíciles conocidos. [8] [9] La firma que se describe a continuación tiene una reducción demostrable al Problema del vector más corto en una red ideal . [10] Esto significa que si se puede encontrar un ataque en el criptosistema Ring-LWE, entonces toda una clase de supuestos problemas computacionales duros tendrán una solución. [11]
La primera firma basada en RLWE fue desarrollada por Lyubashevsky en su artículo "Fiat-Shamir with Aborts: Applications to Lattice and Factoring-Based Signatures" [12] y refinada en "Lattice Signatures Without Trapdoors" en 2011. [13] Varias mejoras y han seguido variantes. Este artículo destaca la estructura matemática fundamental de las firmas RLWE y sigue el trabajo original de Lyubashevsky y el trabajo de Guneysu, Lyubashevsky y Popplemann ( GLP ). [10] Esta presentación se basa en una actualización de 2017 del esquema GLP llamado GLYPH. [14]
Un RLWE-SIG trabaja en el anillo cociente de polinomios módulo a grado n polinomio Φ (x) con coeficientes en el campo finito Z q para un primo impar q (es decir, el anillo Z q [x] / Φ (x)). [13] La multiplicación y la suma de polinomios funcionarán de la manera habitual con los resultados de una multiplicación reducida mod Φ (x). Para esta presentación, un polinomio típico se expresa como:
El campo Z q tiene sus elementos representativos en el conjunto {- (q-1) / 2, ...- 1, 0, 1, ... (q-1) / 2}. Cuando n es una potencia de 2, el polinomio Φ (x) será el polinomio ciclotómico x n + 1. Son posibles otras elecciones de n pero los polinomios ciclotómicos correspondientes son más complicados o su seguridad no está tan bien estudiada.
Generación de polinomios "pequeños".
Una firma RLWE utiliza polinomios que se consideran "pequeños" con respecto a una medida llamada " norma infinita ". La norma de infinito para un polinomio es simplemente el valor absoluto más grande de los coeficientes del polinomio cuando esos coeficientes se ven como números enteros en Z en lugar de Z q . [10] El algoritmo de firma creará polinomios aleatorios que son pequeños con respecto a un límite de norma infinito particular. Esto se hace fácilmente generando aleatoriamente todos los coeficientes del polinomio (a 0 , ..., a n-1 ) de una manera que se garantiza o es muy probable que sea menor o igual que este límite. En la literatura sobre el aprendizaje en anillo con errores, hay dos formas comunes de hacer esto: [13]
- Uso de muestreo uniforme : los coeficientes del polinomio pequeño se muestrean uniformemente a partir de un conjunto de coeficientes pequeños. Sea b un número entero mucho menor que q. Si elegimos aleatoriamente coeficientes polinomiales del conjunto: {-b, -b + 1, -b + 2. ... -2, -1, 0, 1, 2, ..., b-2, b-1, b} la norma infinita del polinomio será ≤ (b).
- Uso de muestreo gaussiano discreto: para un número entero impar q, los coeficientes se eligen aleatoriamente mediante el muestreo del conjunto {- (q-1) / 2 a (q-1) / 2} de acuerdo con una distribución gaussiana discreta con media 0 y distribución parámetro σ. Las referencias proporcionan más detalles sobre este método.
En la firma GLYPH de RLWE que se usa como ejemplo a continuación, los coeficientes para los polinomios "pequeños" usarán el método de muestreo uniforme y el valor b será mucho menor que el valor q. [10]
Hash a un polinomio "pequeño"
La mayoría de los algoritmos de firma RLWE también requieren la capacidad de dividir criptográficamente cadenas de bits arbitrarias en pequeños polinomios de acuerdo con alguna distribución. El siguiente ejemplo utiliza una función hash, POLYHASH (ω), que acepta una cadena de bits, ω, como entrada y genera un polinomio con n coeficientes de manera que exactamente k de estos coeficientes tienen un valor absoluto mayor que cero y menor que un límite entero b (véase más arriba).
Muestreo de rechazo
Una característica clave de los algoritmos de firma RLWE es el uso de una técnica conocida como muestreo de rechazo . [13] [12] En esta técnica, si la norma infinita de un polinomio de firma excede un límite fijo, β, ese polinomio se descartará y el proceso de firma comenzará de nuevo. Este proceso se repetirá hasta que la norma de infinito del polinomio de firma sea menor o igual que el límite. El muestreo de rechazo asegura que la firma de salida no se correlacione de manera explotable con los valores de clave secreta del firmante.
En el ejemplo que sigue, el límite, β, será (b - k), donde b es el rango del muestreo uniforme descrito anteriormente y k será el número de coeficientes distintos de cero permitidos en un polinomio "aceptado" [10 ]
Otros parámetros
Siguiendo a GLYPH y como se señaló anteriormente, el grado máximo de los polinomios será n-1 y por lo tanto tendrá n coeficientes. [10] Los valores típicos para n son 512 y 1024. [10] Los coeficientes de estos polinomios serán del campo F q donde q es un primo impar congruente con 1 mod 4. Para n = 1024, GLYPH establece q = 59393 , b = 16383 yk el número de coeficientes distintos de cero en la salida de Polyhash es igual a 16. [14] El número de coeficientes distintos de cero k producido por la función hash es igual a 32 para ambos casos. [10] La seguridad del esquema de firmas está estrechamente ligada a los tamaños relativos de n, q, by k. Los detalles sobre la configuración de estos parámetros se pueden encontrar en las referencias 5 y 6 a continuación. [13] [10] [14]
Como se señaló anteriormente, el polinomio Φ (x) que define el anillo de polinomios utilizado será x n + 1. Finalmente, a (x) será un polinomio fijo y elegido al azar con coeficientes del conjunto {- (q-1) / 2 a (q-1) / 2}. El polinomio a (x) debe elegirse de una manera " Nothing Up My Sleeve ", como el hash unidireccional de la salida de un generador de números aleatorios de ruido verdadero (TRNG) o el uso de la expansión digital de constantes matemáticas bien conocidas como pi o mi. Todos los firmantes y verificadores de firmas conocerán n, q, b, k, Φ (x), a (x) y β = bk.
Generación de claves públicas
Una entidad que desee firmar mensajes genera su clave pública mediante los siguientes pasos:
- Genere dos polinomios pequeños s (x) ye (x) con coeficientes elegidos uniformemente del conjunto {-b, ...- 1, 0, 1, ..., b}
- Calcule t (x) = a (x) · s (x) + e (x)
- Distribuir t (x) como la clave pública de la entidad
Los polinomios s (x) ye (x) sirven como clave privada y t (x) es la clave pública correspondiente. La seguridad de este esquema de firma se basa en el siguiente problema. Dado un polinomio t (x), encuentre polinomios pequeños f 1 (x) y f 2 (x) tales que: a (x) · f 1 (x) + f 2 (x) = t (x)
Si este problema es difícil de resolver, el esquema de firmas será difícil de falsificar. [Consulte el artículo de Wikipedia sobre aprendizaje en anillo con errores o criptografía de celosía ideal para obtener más detalles sobre la dificultad teórica de este problema]
Generación de firmas
Siguiendo a GLYPH, [14] para firmar un mensaje m expresado como una cadena de bits, la entidad firmante hace lo siguiente:
- Genere dos polinomios pequeños y 1 (x) y y 2 (x) con coeficientes del conjunto {-b, ..., 0, ...., b}
- Calcule w (x) = a (x) · y 1 (x) + y 2 (x)
- Asigna w (x) en una cadena de bits ω
- Calcule c (x) = POLYHASH (ω | m) (Este es un polinomio con k coeficientes distintos de cero. El "|" denota la concatenación de cadenas)
- Calcular z 1 (x) = s (x) · c (x) + y 1 (x)
- Calcular z 2 (x) = e (x) · c (x) + y 2 (x)
- Hasta que las normas infinitas de z 1 (x) y z 2 (x) ≤ β = ( B - k) vaya al paso 1. (Este es el paso de muestreo de rechazo mencionado anteriormente)
- La firma es el triple de polinomios c (x), z 1 (x) y z 2 (x)
- Transmita el mensaje junto con c (x), z 1 (x) y z 2 (x) al verificador.
Verificación de firma
Siguiendo a GLYPH, [14] para verificar un mensaje m expresado como una cadena de bits, la entidad verificadora debe poseer la clave pública del firmante (t (x)), la firma (c (x), z 1 (x), z 2 ( x)) y el mensaje m. El verificador hace lo siguiente:
- Verifique que las normas de infinito de z 1 (x) y z 2 (x) ≤ β , si no rechazan la firma.
- Calcule w '(x) = a (x) · z 1 (x) + z 2 (x) - t (x) c (x)
- Asigna w '(x) en una cadena de bits ω'
- Calcular c '(x) = POLYHASH (ω' | m)
- Si c '(x) ≠ c (x) rechaza la firma, de lo contrario acepte la firma como válida.
Darse cuenta de:
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) (como se define arriba)
Esta breve derivación demuestra que el proceso de verificación tendrá c '(x) = c (x) si la firma no fue alterada.
Nuevos desarrollos
El esquema de firma GLYPH descrito en este documento sigue de cerca el trabajo de Lyubashevsky, Gunesyu y Popplemen de 2011 y 2012. Hay una serie de otras variaciones de su trabajo. Éstas incluyen:
- Trabajo de Bai y Galbraith en firmas cortas documentadas aquí . [15]
- Trabajo de Akleylek, Bindel, Buchmann, Kramer y Marson en pruebas de seguridad para la firma con menos supuestos de seguridad y documentado aquí . [dieciséis]
Otro enfoque para las firmas basadas en celosías sobre anillos es una variante de la familia NTRU patentada de criptografía basada en celosías. El ejemplo principal de este enfoque es una firma conocida como Bimodal Lattice Signature Scheme (BLISS). Fue desarrollado por Ducas, Durmas, Lepoint y Lyubashevsky y documentado en su artículo "Lattice Signatures and Bimodal Gaussians". [17] Ver esquema de firma BLISS
Referencias
- ↑ a b c d Dahmen-Lhuissier, Sabine. "ETSI - Criptografía cuántica segura" . ETSI . Consultado el 5 de julio de 2015 .
- ^ Shah, Agam. "Reclamación de avance de la computación cuántica de IBM" . Consultado el 1 de junio de 2015 .
- ^ Markoff, John (4 de marzo de 2015). "Los investigadores informan un hito en el desarrollo de la computadora cuántica" . The New York Times . ISSN 0362-4331 . Consultado el 5 de julio de 2015 .
- ^ Beckman, David; Chari, Amalavoyal N .; Devabhaktuni, Srikrishna; Preskill, John (1996). "Redes eficientes para factorización cuántica". Physical Review A . 54 (2): 1034–1063. arXiv : quant-ph / 9602016 . Código Bibliográfico : 1996PhRvA..54.1034B . doi : 10.1103 / PhysRevA.54.1034 . ISSN 1050-2947 . PMID 9913575 . S2CID 2231795 .
- ^ Smolin, John A .; Smith, Graeme; Vargo, Alexander (11 de julio de 2013). "Simplificación de la factorización cuántica". Naturaleza . 499 (7457): 163–165. arXiv : 1301.7007 . Código Bibliográfico : 2013Natur.499..163S . doi : 10.1038 / nature12290 . ISSN 0028-0836 . PMID 23846653 . S2CID 4422110 .
- ^ a b "Introducción" . pqcrypto.org . Consultado el 5 de julio de 2015 .
- ^ "El problema del aprendizaje con errores" (PDF) . www.cims.nyu.edu . Consultado el 24 de mayo de 2015 .
- ^ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "Sobre celosías ideales y aprendizaje con errores sobre anillos". En Proc. De EUROCRYPT, Volumen 6110 de LNCS : 1–23. CiteSeerX 10.1.1.297.6108 .
- ^ "¿Qué significa la" advertencia "de GCHQ para la criptografía de celosía?" . www.cc.gatech.edu . Archivado desde el original el 6 de julio de 2015 . Consultado el 5 de julio de 2015 .
- ^ a b c d e f g h yo Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Criptografía práctica basada en celosía: un esquema de firma para sistemas integrados". En Prouff, Emmanuel; Schaumont, Patrick (eds.). Hardware criptográfico y sistemas integrados - CHES 2012 . Apuntes de conferencias en Ciencias de la Computación. 7428 . Springer Berlín Heidelberg. págs. 530–547. doi : 10.1007 / 978-3-642-33027-8_31 . ISBN 978-3-642-33026-1.
- ^ Micciancio, Daniele (1998). "El vector más corto en una red es difícil de aproximar dentro de alguna constante" . En Proc. 39º Simposio sobre fundamentos de la informática : 92–98.
- ^ a b Lyubashevsky, Vadim (1 de enero de 2009). "Fiat-Shamir con abortos: aplicaciones a firmas basadas en celosía y factoring". En Matsui, Mitsuru (ed.). Avances en Criptología - ASIACRYPT 2009 . Apuntes de conferencias en Ciencias de la Computación. 5912 . Springer Berlín Heidelberg. págs. 598–616. doi : 10.1007 / 978-3-642-10366-7_35 . ISBN 978-3-642-10365-0.
- ^ a b c d e Lyubashevsky, Vadim (2011). "Firmas de celosía sin trampillas" . Cite journal requiere
|journal=
( ayuda ) - ^ a b c d e Chopra, Arjun (2017). "GLYPH: una nueva instanciación del esquema de firma digital GLP" . Archivo electrónico de la Asociación Internacional de Investigación Criptográfica . Archivado desde el original (PDF) el 26 de agosto de 2017 . Consultado el 26 de agosto de 2017 .
- ^ "Archivo de Cryptology ePrint: Informe 2013/838" . eprint.iacr.org . Consultado el 17 de enero de 2016 .
- ^ "Archivo de Cryptology ePrint: Informe 2015/755" . eprint.iacr.org . Consultado el 17 de enero de 2016 .
- ^ "Archivo de Cryptology ePrint: Informe 2013/383" . eprint.iacr.org . Consultado el 17 de enero de 2016 .