Hispanopedia Wiki
Articulo de referencia

Aprendizaje en anillo con firma de errores

Las firmas digitales son un medio para proteger la información digital de modificaciones intencionadas y para autenticar su origen. La criptografía de clave pública ofrece un am...

Hispanopedia WikiContenido en espanolLectura gratuita

Las firmas digitales son un medio para proteger la información digital de modificaciones intencionadas y para autenticar su origen. La criptografía de clave pública ofrece un amplio conjunto de algoritmos criptográficos para crear firmas digitales. Sin embargo, las firmas de clave pública primarias actualmente en uso ( RSA y firmas de curva elíptica) se volverán completamente inseguras si los científicos 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 resistir ataques de criptografía cuántica. Se están creando varios algoritmos de firma digital postcuántica basados ​​en problemas complejos en retículos para reemplazar las firmas RSA y de curva elíptica de uso común. Un subconjunto de estos esquemas basados ​​en retículos se basa en un problema conocido como aprendizaje de anillos con errores . Las firmas digitales basadas en aprendizaje de anillos con errores se encuentran entre las firmas postcuánticas con los tamaños de clave pública y firma más pequeños.

Fondo

Los avances en computación cuántica durante la última década y las perspectivas optimistas para la existencia de computadoras cuánticas reales en los próximos 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 es RSA . Su seguridad se basa en la dificultad clásica de factorizar el producto de dos primos grandes y desconocidos en sus primos constituyentes. Se cree que el problema de la factorización de enteros es intratable en cualquier ordenador convencional si los primos se eligen al azar y son suficientemente grandes. Sin embargo, para factorizar el producto de dos primos de n bits, un ordenador cuántico con aproximadamente 6n bits de memoria lógica de cúbits y capaz de ejecutar un programa conocido como algoritmo de Shor puede realizar la tarea fácilmente. [ 5 ] El algoritmo de Shor también puede romper rápidamente las firmas digitales basadas en el problema del logaritmo discreto y el problema más esotérico del logaritmo discreto de curva elíptica . En efecto, un ordenador cuántico relativamente pequeño 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 desconocemos cuándo existirá una computadora cuántica capaz de romper RSA y otros algoritmos de firma digital, durante la última década se ha investigado activamente para crear algoritmos criptográficos que sigan siendo seguros incluso cuando un atacante disponga de los recursos de una computadora cuántica. [ 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 con errores en anillo. 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 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 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 problemas computacionales supuestamente difíciles tendrá una solución. [ 11 ]

La primera firma basada en RLWE fue desarrollada por Lyubashevsky en su artículo "Fiat-Shamir con abortos: aplicaciones a firmas basadas en retículos y factorización" [ 12 ] y refinada en "Firmas de retículos sin trampas" en 2011. [ 13 ] Posteriormente se realizaron varios refinamientos 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 opera 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 los resultados de una multiplicación reducidos módulo Φ(x). Para esta presentación, un polinomio típico se expresa como:

a(incógnita)=a0+a1incógnita+a2incógnita2+…+anorte−3incógnitanorte−3+anorte−2incógnitanorte−2+anorte−1incógnitanorte−1{\displaystyle 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 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. Son posibles otras elecciones de n, pero los polinomios ciclotómicos correspondientes son más complejos 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 infinito ". La norma infinito para un polinomio es simplemente el mayor valor absoluto de los coeficientes del polinomio cuando esos coeficientes se consideran 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 particular de la norma infinito. Esto se hace fácilmente generando aleatoriamente todos los coeficientes del polinomio (a 0 , ..., a n-1 ) de una manera que está garantizada o es muy probable que sean menores o iguales a este límite. En la literatura sobre Ring Learning with Errors, hay dos formas comunes de hacer esto: [ 13 ]

  • Usando muestreo uniforme : los coeficientes del pequeño polinomio se muestrean uniformemente de un conjunto de coeficientes pequeños. Sea b un entero mucho menor que q. Si elegimos aleatoriamente coeficientes del polinomio del conjunto: { -b, -b+1, -b+2, ... -2, -1, 0, 1, 2, ... , b-2, b-1, b} la norma infinito del polinomio será ≤ (b).
  • Mediante muestreo gaussiano discreto: para un entero impar q, los coeficientes se eligen aleatoriamente mediante muestreo del conjunto { -(q-1)/2 a (q-1)/2 } según una distribución gaussiana discreta con media 0 y parámetro de distribución σ. Las referencias proporcionan más detalles sobre este método.

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 ]

Hashing a un polinomio "pequeño"

La mayoría de los algoritmos de firma RLWE también requieren la capacidad de convertir cadenas de bits arbitrarias en polinomios pequeños mediante funciones hash criptográficas , siguiendo alguna distribución. El siguiente ejemplo utiliza una función hash, POLYHASH(ω), que recibe como entrada una cadena de bits, ω, y genera un polinomio con n coeficientes, de modo 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 por rechazo . [ 13 ] [ 12 ] En esta técnica, si la norma infinito de un polinomio de firma excede un límite fijo, β, dicho polinomio se descarta y el proceso de firma se reinicia. Este proceso se repite hasta que la norma infinito del polinomio de firma sea menor o igual al límite. El muestreo por rechazo garantiza que la firma resultante no esté correlacionada de forma 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 ].

Otros parámetros

Siguiendo a GLYPH y como se indicó 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 no nulos en la salida de Polyhash igual a 16. [ 14 ] El número de coeficientes no nulos k producido 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 indicó anteriormente, el polinomio Φ(x) que define el anillo de polinomios utilizados 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 manera " sin trucos ", como por ejemplo, aplicando una función hash unidireccional a la salida de un generador de números aleatorios de ruido verdadero (TRNG) o utilizando la expansión digital de constantes matemáticas conocidas como pi o e. Todos los firmantes y verificadores de firmas conocerán n, q, b, k, Φ(x), a(x) y β = bk.

Generación de clave pública

Una entidad que desee firmar mensajes genera su clave pública siguiendo los siguientes pasos:

  1. Genera dos polinomios pequeños s(x) y e(x) con coeficientes elegidos uniformemente del conjunto {-b,...-1, 0, 1, ..., b}.
  2. Calcula t(x) = a(x)·s(x) + e(x)
  3. Distribuye t(x) como la clave pública de la entidad.

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), encontrar polinomios pequeños f₁ ( x) y f₂ ( x) tales que: a(x)·f₁ ( x) + f₂ ( x) = t(x).

Si este problema es difícil de resolver, entonces el esquema de firma será difícil de falsificar. [ Para obtener más detalles sobre la dificultad teórica de este problema, consulte el artículo de Wikipedia sobre Aprendizaje en Anillo con Errores o Criptografía de Retículo Ideal ].

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:

  1. Genera dos polinomios pequeños y 1 (x) e y 2 (x) con coeficientes del conjunto {-b, ..., 0, ..., b}.
  2. Calcula w(x) = a(x)·y 1 (x) + y 2 (x)
  3. Mapea w(x) en una cadena de bits ω
  4. Calcula c(x) = POLYHASH(ω | m) (Este es un polinomio con k coeficientes distintos de cero. El símbolo "|" denota la concatenación de cadenas).
  5. Calcula z 1 (x) = s(x)·c(x) + y 1 (x)
  6. Calcula z 2 (x) = e(x)·c(x) + y 2 (x)
  7. Hasta que las normas de infinito de z 1 (x) y z 2 (x) ≤ β = ( B - k) vaya al paso 1. (Este es el paso de muestreo por rechazo mencionado anteriormente)
  8. La signatura es la terna de polinomios c(x), z 1 (x) y z 2 (x).
  9. Transmita el mensaje junto con c(x), z 1 (x) y z 2 (x) al verificador.

Verificación de firma

Según 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 realiza lo siguiente:

  1. Verifica que las normas de infinito de z 1 (x) y z 2 (x) ≤ β , si no, rechaza la firma.
  2. Calcula w'(x) = a(x)·z 1 (x) + z 2 (x) - t(x)c(x)
  3. Mapea w'(x) en una cadena de bits ω'.
  4. Calcular c'(x) = POLYHASH(ω' | m)
  5. Si c'(x) ≠ c(x) rechace la firma, de lo contrario acepte la firma como válida.

Observa que:

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 definió anteriormente)

Esta breve derivación demuestra que el proceso de verificación tendrá c'(x) = c(x) si la firma no fue manipulada.

Nuevos desarrollos

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 en su trabajo, entre las que se incluyen:

  • El trabajo de Bai y Galbraith sobre firmas cortas está documentado aquí . [ 15 ]
  • Trabajo de Akleylek, Bindel, Buchmann, Kramer y Marson sobre pruebas de seguridad para la firma con menos supuestos de seguridad y documentado aquí . [ 16 ]

Otro enfoque para firmas basado en retículos sobre anillos es una variante de la familia patentada NTRU de criptografía basada en retículos. El ejemplo principal de este enfoque es una firma conocida como Esquema de Firma de Retículo Bimodal (BLISS). Fue desarrollada por Ducas, Durmas, Lepoint y Lyubashevsky y documentada en su artículo "Firmas de Retículo y Gaussianas Bimodales". [ 17 ] Véase Esquema de firma BLISS

Referencias

  1. ^ Dahmen -Lhuissier, Sabine . "ETSI - Criptografía cuántica segura" . ETSI . Consultado el 5 de julio de 2015 .
  2. ↑ Shah, Agam. "Afirmación de IBM sobre un avance en computación cuántica" . Archivado del original el 23 de septiembre de 2015. Consultado el 1 de junio de 2015 .
  3. ↑ Markoff, John (4 de marzo de 2015). "Investigadores informan de un hito en el desarrollo de la computadora cuántica" . The New York Times . ISSN 0362-4331 . Consultado el 5 de julio de 2015 . 
  4. ↑ 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 . Bibcode : 1996PhRvA..54.1034B . doi : 10.1103/PhysRevA.54.1034 . ISSN 1050-2947 . PMID 9913575 . S2CID 2231795 .   
  5. ↑ Smolin, John A.; Smith, Graeme; Vargo, Alexander (11 de julio de 2013). "Simplificando en exceso la factorización cuántica". Nature . 499 ( 7457): 163– 165. arXiv : 1301.7007 . Bibcode : 2013Natur.499..163S . doi : 10.1038/nature12290 . ISSN 0028-0836 . PMID 23846653. S2CID 4422110 .   
  6. 1 2 "Introducción" . pqcrypto.org . Consultado el 5 de julio de 2015 .
  7. ↑ "El problema del aprendizaje con errores" (PDF) . www.cims.nyu.edu . Consultado el 24 de mayo de 2015 .
  8. ↑ Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "Sobre retículos ideales y aprendizaje con errores sobre anillos". En Gilbert, Henri (ed.). Avances en criptología – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. pp. 1–23 . CiteSeerX 10.1.1.297.6108 . doi : 10.1007/978-3-642-13190-5_1 . ISBN    978-3-642-13189-9.
  9. ↑ "¿Qué significa la "historia de advertencia" del GCHQ para la criptografía reticular?" . www.cc.gatech.edu . Archivado del original el 6 de julio de 2015 . Consultado el 5 de julio de 2015 .
  10. 1 2 3 4 5 6 7 8 9 Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Criptografía práctica basada en retículos: un esquema de firma para sistemas embebidos". En Prouff, Emmanuel; Schaumont, Patrick (eds.). Hardware criptográfico y sistemas embebidos – CHES 2012. Lecture Notes in Computer Science. Vol. 7428. Springer Berlin Heidelberg. pp. 530–547 . doi : 10.1007/978-3-642-33027-8_31 . ISBN   978-3-642-33026-1.
  11. ↑ Micciancio, Daniele (1998). "El vector más corto en una red es difícil de aproximar con una constante" . En Actas del 39.º Simposio sobre Fundamentos de la Informática : 92–98 .
  12. 1 2 Lyubashevsky, Vadim (2009-01-01). "Fiat-Shamir con abortos: aplicaciones a firmas basadas en retículos y factorización". En Matsui, Mitsuru (ed.). Avances en criptología – ASIACRYPT 2009. Lecture Notes in Computer Science. Vol. 5912. Springer Berlin Heidelberg. pp. 598–616 . doi : 10.1007/978-3-642-10366-7_35 . ISBN   978-3-642-10365-0.
  13. 1 2 3 4 5 Lyubashevsky, Vadim (2011). "Firmas reticulares sin puertas traseras" . Cryptology ePrint Archive .
  14. 1 2 3 4 5 Chopra, Arjun (2017). "GLYPH: Una nueva instanciación del esquema de firma digital GLP" (PDF) . Archivo de preimpresiones de la Asociación Internacional de Investigación Criptográfica . Archivado del original el 28 de agosto de 2017. Recuperado el 26 de agosto de 2017 .{{cite web}}: CS1 maint: bot: estado de la URL original desconocido ( enlace )
  15. ↑ "Archivo de preimpresiones de criptología: Informe 2013/838" . eprint.iacr.org . Consultado el 17 de enero de 2016 .
  16. ↑ "Archivo de preimpresiones de criptología: Informe 2015/755" . eprint.iacr.org . Consultado el 17 de enero de 2016 .
  17. ↑ "Archivo de preimpresiones de criptología: Informe 2013/383" . eprint.iacr.org . Consultado el 17 de enero de 2016 .