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 rico conjunto de diferentes algoritmos criptográficos para crear firmas digitales. Sin embargo, las principales firmas de clave pública actualmente en uso ( RSA y firmas de curva elíptica) se volverán completamente inseguras si los científicos alguna vez logran construir una computadora cuántica de tamaño moderado . [1] La criptografía poscuántica es 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 poscuánticos basados en problemas complejos en redes que reemplazan las firmas RSA y de curva elíptica comúnmente utilizadas. Un subconjunto de estos esquemas basados en celosías 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 poscuánticas con la clave pública y los tamaños de firma más pequeños.
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 rompería fácilmente 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 factorización de números enteros es intratable en cualquier computadora convencional si los números primos se eligen al azar y son 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 de qubits lógicos 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 del logaritmo discreto y el problema más esotérico del logaritmo discreto de la curva elíptica . 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 y la integridad de la información en Internet hoy en día.
Aunque no sabemos cuándo existirá una computadora cuántica capaz de romper RSA y otros algoritmos de firma digital, durante la última década se han realizado investigaciones activas para crear algoritmos criptográficos que permanezcan seguros incluso cuando un atacante tiene los recursos de una computadora cuántica a su alcance. desecho. [1] [6] Esta nueva área de la criptografía se llama criptografía postcuántica o criptografía cuántica segura . [1] [6] Este artículo trata sobre una clase de estos algoritmos: firmas digitales basadas en el problema Ring Learning with Errors. Oded Regev introdujo el uso del problema general de aprendizaje con errores en criptografía en 2005 y ha sido la fuente de varios diseños criptográficos. [7]
Los creadores de la base de criptografía Ring-based Learning with Errors (RLWE) creen que una característica importante de estos algoritmos basados en Ring-Learning with Errors 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 difíciles 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] Una serie de 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 BPL llamada GLYPH. [14]
Un RLWE-SIG funciona en el anillo cociente de polinomios módulo un polinomio de grado n Φ(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 suma de polinomios funcionará de la manera habitual con 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 opciones de n, pero los polinomios ciclotómicos correspondientes son más complicados o su seguridad no está tan bien estudiada.
Una firma RLWE utiliza polinomios que se consideran "pequeños" con respecto a una medida llamada " norma del infinito ". La norma infinita para un polinomio es simplemente el valor absoluto más grande de los coeficientes del polinomio cuando esos coeficientes se consideran 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 , ..., an-1 ) de una manera que se garantiza o es muy probable que sea menor o igual a este límite. En la literatura sobre Ring Learning con errores, hay dos formas comunes de hacer esto: [13]
En el GLYPH de la firma RLWE que se utiliza como ejemplo a continuación, los coeficientes para los polinomios "pequeños" utilizarán el método de muestreo uniforme y el valor b será mucho menor que el valor q. [10]
La mayoría de los algoritmos de firma RLWE también requieren la capacidad de codificar criptográficamente cadenas de bits arbitrarias en pequeños polinomios según 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 tal que exactamente k de estos coeficientes tienen un valor absoluto mayor que cero y menor que un entero enlazado b (véase más arriba).
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á nuevamente. Este proceso se repetirá hasta que la norma infinita del polinomio característico sea menor o igual que el límite. El muestreo de rechazo garantiza que la firma de salida no esté correlacionada de manera explotable con los valores de clave secreta del firmante.
En el siguiente ejemplo, 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 ]
Siguiendo el GLIFO y como se señaló anteriormente, el grado máximo de los polinomios será n-1 y por lo tanto tendrán 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 y k 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 producidos por la función hash es igual a 32 para ambos casos. [10] La seguridad del esquema de firma está estrechamente ligada a los tamaños relativos de n, q, b y 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 aleatoriamente con coeficientes del conjunto { -(q-1) /2 a (q-1)/2 }. El polinomio a(x) debe elegirse de una manera " nada bajo mi manga ", como mediante un hash unidireccional de la salida de un generador de números aleatorios de ruido verdadero (TRNG) o utilizando la expansión digital de constantes matemáticas bien conocidas como pi o mi. Todos los firmantes y verificadores de firmas sabrán n, q, b, k, Φ(x), a(x) y β = bk.
Una entidad que desee firmar mensajes genera su clave pública mediante los siguientes pasos:
Los polinomios s(x) y e(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, entonces el esquema de firma 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]
Siguiendo GLYPH, [14] para firmar un mensaje m expresado como una cadena de bits, la entidad firmante hace lo siguiente:
Siguiendo 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:
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 manipulada.
El esquema de firma GLYPH descrito en este documento sigue de cerca el trabajo de Lyubashevsky, Gunesyu y Popplemen de 2011 y 2012. Hay otras variaciones de su trabajo. Éstas incluyen:
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 principal ejemplo de este enfoque es una firma conocida como Esquema de firma de celosía bimodal (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
{{cite web}}: Mantenimiento CS1: bot: estado de la URL original desconocido ( enlace )