Las firmas digitales son un medio para proteger la información digital de modificaciones intencionales y para autenticar la fuente de la 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 principales firmas de clave pública que se utilizan actualmente ( 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 postcuántica es una clase de algoritmos criptográficos diseñados para ser resistentes a los ataques de una criptografía cuántica. Se están creando varios algoritmos de firma digital postcuántica basados en problemas difíciles en redes que reemplazan las firmas RSA y de curva elíptica de uso común. Un subconjunto de estos esquemas basados en redes se basa en un problema conocido como aprendizaje en anillo con errores . Las firmas digitales basadas en aprendizaje en anillo con errores se encuentran entre las firmas postcuánticas con los tamaños de clave pública y firma más pequeños.
Los avances en computación cuántica durante la última década y las perspectivas optimistas de que dentro de 20 años existan computadoras cuánticas reales 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 la 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 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 primos se eligen al azar y son suficientemente grandes. Sin embargo, para factorizar el producto de dos primos de n bits, una computadora cuántica con aproximadamente 6n bits de memoria lógica de qubits y capaz de ejecutar un programa conocido como el algoritmo de Shor realizará fácilmente la tarea. [5] El algoritmo de Shor también puede romper rápidamente las firmas digitales basadas 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 e integridad de la información en Internet hoy en día.
Aunque no sabemos cuándo existirá un ordenador cuántico capaz de descifrar el RSA y otros algoritmos de firma digital, en la última década se han llevado a cabo investigaciones activas para crear algoritmos criptográficos que sigan siendo seguros incluso cuando un atacante tenga a su disposición los recursos de un ordenador cuántico. [1] [6] Esta nueva área de la criptografía se denomina criptografía postcuántica o criptografía cuántica segura . [1] [6] Este artículo trata sobre una clase de estos algoritmos: las 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 del algoritmo Ring-based Learning with Errors (RLWE) para criptografía 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 descrita 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 al 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] A esto le siguieron una serie de mejoras y 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 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 cuerpo 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 resultados de una multiplicación reducida módulo Φ(x). Para esta presentación, un polinomio típico se expresa como:
El cuerpo 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. Otras opciones de n son posibles 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 de infinito ". 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 de 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 a este límite. En la literatura sobre aprendizaje de anillos con errores, hay dos formas comunes de hacer esto: [13]
En la firma RLWE GLYPH utilizada 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 convertir criptográficamente cadenas de bits arbitrarias en pequeños polinomios de acuerdo con alguna distribución. El ejemplo siguiente 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 tengan un valor absoluto mayor que cero y menor que un límite entero b (ver 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 de infinito de un polinomio de firma excede un límite fijo, β, ese polinomio será descartado 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 al límite. El muestreo de rechazo asegura que la firma de salida no esté correlacionada de manera explotable con los valores de la 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].
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 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 módulo 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 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 vinculada 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 elegido aleatoriamente y fijo con coeficientes del conjunto { -(q-1)/2 a (q-1)/2 }. El polinomio a(x) debe elegirse de una manera " sin tener nada en la manga ", como por ejemplo mediante un algoritmo hash unidireccional de la salida de un generador de números aleatorios de ruido real (TRNG) o utilizando la expansión digital de constantes matemáticas bien conocidas, como pi o e. Todos los firmantes y verificadores de firmas conocerán n, q, b, k, Φ(x), a(x) y β = bk.
Una entidad que desea firmar mensajes genera su clave pública a través de 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 de anillos con errores o criptografía de red 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 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:
Tenga en cuenta que:
a(x)· z1 (x) + z2 (x) - t(x)c(x) = a(x)·[s(x)·c(x) + y1 ( x)] + z2 (x) - [a(x)·s(x) + e(x)]c(x)
= a(x)·y1 ( x)+z2 ( 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.
El esquema de firmas GLYPH descrito en este documento sigue de cerca el trabajo de Lyubashevsky, Gunesyu y Popplemen de 2011 y 2012. Existen otras variaciones de su trabajo, entre ellas:
Otro enfoque para las firmas basadas en retículas sobre anillos es una variante de la familia NTRU patentada de criptografía basada en retículas. El principal ejemplo de este enfoque es una firma conocida como Esquema de Firma de Retícula Bimodal (BLISS). Fue desarrollado por Ducas, Durmas, Lepoint y Lyubashevsky y documentado en su artículo "Firmas de Retícula y Gaussianas Bimodales". [17] Véase el esquema de firma BLISS
{{cite web}}: CS1 maint: bot: estado de URL original desconocido ( enlace )