Aprendizaje de anillos con errores

Problema computacional posiblemente útil para la criptografía post-cuántica

En criptografía post-cuántica , el aprendizaje de anillos con errores ( RLWE ) es un problema computacional que sirve como base de nuevos algoritmos criptográficos , como NewHope , diseñado para proteger contra el criptoanálisis por parte de computadoras cuánticas y también para proporcionar la base para el cifrado homomórfico . La criptografía de clave pública se basa en la construcción de problemas matemáticos que se cree que son difíciles de resolver si no hay más información disponible, pero son fáciles de resolver si se conoce alguna información utilizada en la construcción del problema. Algunos problemas de este tipo que se utilizan actualmente en criptografía corren el riesgo de ser atacados si alguna vez se logran construir computadoras cuánticas lo suficientemente grandes, por lo que se buscan problemas resistentes. El cifrado homomórfico es una forma de cifrado que permite el cálculo en texto cifrado, como la aritmética en valores numéricos almacenados en una base de datos cifrada.

RLWE se denomina más apropiadamente aprendizaje con errores sobre anillos y es simplemente el problema de aprendizaje con errores más grande (LWE) especializado en anillos polinomiales sobre campos finitos. ^[1] Debido a la presunta dificultad de resolver el problema RLWE incluso en una computadora cuántica, la criptografía basada en RLWE puede formar la base fundamental para la criptografía de clave pública en el futuro, tal como la factorización de enteros y el problema del logaritmo discreto han servido como base para la criptografía de clave pública desde principios de la década de 1980. ^[2] Una característica importante de basar la criptografía en el problema de aprendizaje con errores en anillo es el hecho de que la solución al problema RLWE se puede utilizar para resolver una versión del problema del vector más corto (SVP) en una red (se ha presentado una reducción de tiempo polinomial de este problema SVP al problema RLWE ^[1] ).

Fondo

La seguridad de la criptografía moderna, en particular la criptografía de clave pública , se basa en la supuesta intratabilidad de resolver ciertos problemas computacionales si el tamaño del problema es lo suficientemente grande y la instancia del problema a resolver se elige aleatoriamente. El ejemplo clásico que se ha utilizado desde la década de 1970 es el problema de factorización de números enteros . Se cree que es computacionalmente intratable factorizar el producto de dos números primos si esos números primos son lo suficientemente grandes y se eligen al azar. ^[3] A partir de 2015, la investigación ha llevado a la factorización del producto de dos primos de 384 bits, pero no al producto de dos primos de 512 bits. La factorización de números enteros forma la base del algoritmo criptográfico RSA ampliamente utilizado .

El problema de aprendizaje de anillos con errores (RLWE) se basa en la aritmética de polinomios con coeficientes de un campo finito . ^[1] Un polinomio típico se expresa como: ${\textstyle a(x)}$

${\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\ldots +a_{n-2}x^{n-2}+a_{n-1}x^{n-1}}$

Los polinomios se pueden sumar y multiplicar de la forma habitual. En el contexto RLWE, los coeficientes de los polinomios y todas las operaciones que involucran esos coeficientes se realizarán en un cuerpo finito, típicamente el cuerpo de un entero primo . El conjunto de polinomios sobre un cuerpo finito con las operaciones de adición y multiplicación forma un anillo polinómico infinito ( ). El contexto RLWE trabaja con un anillo cociente finito de este anillo infinito. El anillo cociente es típicamente el anillo cociente (factor) finito formado al reducir todos los polinomios en módulo un polinomio irreducible . Este anillo cociente finito se puede escribir como si muchos autores escribieran . ^[1] ${\textstyle \mathbf {Z} /q\mathbf {Z} =\mathbf {F} _{q}}$ ${\textstyle q}$ ${\textstyle \mathbf {F} _{q}[x]}$ ${\textstyle \mathbf {F} _{q}[x]}$ ${\textstyle \Phi (x)}$ ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$ ${\displaystyle \mathbf {Z} _{q}[x]/\Phi (x)}$

Si el grado del polinomio es , el anillo de cocientes se convierte en el anillo de polinomios de grado menor que módulo con coeficientes de . Los valores , , junto con el polinomio definen parcialmente el contexto matemático del problema RLWE. ${\displaystyle \Phi (x)}$ ${\textstyle n}$ ${\displaystyle n}$ ${\displaystyle \Phi (x)}$ ${\displaystyle F_{q}}$ ${\textstyle n}$ ${\textstyle q}$ ${\displaystyle \Phi (x)}$

Otro concepto necesario para el problema RLWE es la idea de polinomios "pequeños" con respecto a alguna norma. La norma típica utilizada en el problema RLWE se conoce como norma de infinito (también llamada norma uniforme ). La norma de infinito de un polinomio es simplemente el coeficiente más grande del polinomio cuando estos coeficientes se ven como números enteros. Por lo tanto, establece que la norma de infinito del polinomio es . Por lo tanto, es el coeficiente más grande de . ${\displaystyle ||a(x)||_{\infty }=b}$ ${\displaystyle a(x)}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a(x)}$

El concepto final necesario para comprender el problema RLWE es la generación de polinomios aleatorios en y la generación de polinomios "pequeños". Un polinomio aleatorio se genera fácilmente simplemente muestreando aleatoriamente los coeficientes del polinomio de , donde normalmente se representa como el conjunto . ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$ ${\displaystyle n}$ ${\displaystyle \mathbf {F} _{q}}$ ${\displaystyle \mathbf {F} _{q}}$ ${\displaystyle \{-(q-1)/2,...,-1,0,1,...,(q-1)/2\}}$

La generación aleatoria de un polinomio "pequeño" se realiza generando los coeficientes del polinomio de una manera que garantice o haga muy probable que los coeficientes sean pequeños. Cuando es un número entero primo, existen dos formas comunes de hacerlo: ${\displaystyle \mathbf {F} _{q}}$ ${\displaystyle q}$

1. Uso de muestreo uniforme: los coeficientes del polinomio pequeño se muestrean de manera uniforme a partir de un conjunto de coeficientes pequeños. Sea un entero que sea mucho menor que . Si elegimos aleatoriamente coeficientes del conjunto: el polinomio será pequeño con respecto al límite ( ). ${\textstyle b}$ ${\textstyle q}$ ${\textstyle \{-b,-b+1,-b+2,\ldots ,-2,-1,0,1,2,\ldots ,b-2,b-1,b\}}$ ${\textstyle b}$
2. Uso de muestreo gaussiano discreto : para un valor impar de , los coeficientes del polinomio se eligen aleatoriamente mediante un muestreo del conjunto según una distribución gaussiana discreta con media y parámetro de distribución . Las referencias describen con todo detalle cómo se puede lograr esto. Es más complicado que el muestreo uniforme, pero permite una prueba de seguridad del algoritmo. El artículo "Muestreo de gaussianos discretos para criptografía basada en red en un dispositivo restringido" de Dwarakanath y Galbraith proporciona una descripción general de este problema. ^[4] ${\textstyle q}$ ${\textstyle \{-(q-1)/2,\ldots ,(q-1)/2\}}$ ${\displaystyle 0}$ ${\textstyle \sigma }$

El problema de RLWE

El problema RLWE se puede plantear de dos maneras diferentes: una versión de "búsqueda" y una versión de "decisión". Ambas comienzan con la misma construcción. Sea

• ${\displaystyle a_{i}(x)}$sea ​​un conjunto de polinomios aleatorios pero conocidos con coeficientes de todos . ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$ ${\displaystyle \mathbf {F} _{q}}$
• ${\displaystyle e_{i}(x)}$sea ​​un conjunto de pequeños polinomios aleatorios y desconocidos relativos a un límite en el anillo . ${\displaystyle b}$ ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$
• ${\displaystyle s(x)}$sea ​​un pequeño polinomio desconocido relativo a un límite en el anillo . ${\displaystyle b}$ ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$
• ${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$.

La versión de búsqueda implica encontrar el polinomio desconocido dada la lista de pares de polinomios . ${\displaystyle s(x)}$ ${\displaystyle (a_{i}(x),b_{i}(x))}$

La versión de decisión del problema se puede plantear de la siguiente manera. Dada una lista de pares de polinomios , determine si los polinomios se construyeron como o se generaron aleatoriamente a partir de con coeficientes de todos los . ${\displaystyle (a_{i}(x),b_{i}(x))}$ ${\displaystyle b_{i}(x)}$ ${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$ ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$ ${\displaystyle \mathbf {F} _{q}}$

La dificultad de este problema está parametrizada por la elección del polinomio cociente ( ), su grado ( ), el cuerpo ( ) y el límite de pequeñez ( ). En muchos algoritmos de clave pública basados ​​en RLWE, la clave privada será un par de polinomios pequeños y . La clave pública correspondiente será un par de polinomios , seleccionados aleatoriamente entre , y el polinomio . Dados y , debería ser computacionalmente inviable recuperar el polinomio . ${\displaystyle \Phi (x)}$ ${\displaystyle n}$ ${\displaystyle \mathbf {F} _{q}}$ ${\displaystyle b}$ ${\displaystyle s(x)}$ ${\displaystyle e(x)}$ ${\displaystyle a(x)}$ ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$ ${\displaystyle t(x)=(a(x)\cdot s(x))+e(x)}$ ${\displaystyle a(x)}$ ${\displaystyle t(x)}$ ${\displaystyle s(x)}$

Reducción de seguridad

En los casos en que el polinomio es un polinomio ciclotómico , la dificultad de resolver la versión de búsqueda del problema RLWE es equivalente a encontrar un vector corto (pero no necesariamente el vector más corto) en una red ideal formada a partir de elementos de representados como vectores enteros. ^[1] Este problema se conoce comúnmente como el Problema del Vector Más Corto Aproximado (α-SVP) y es el problema de encontrar un vector más corto que α veces el vector más corto. Los autores de la prueba de esta equivalencia escriben: ${\displaystyle \Phi (x)}$ ${\displaystyle \mathbf {Z} [x]/\Phi (x)}$

"... damos una reducción cuántica desde un SVP aproximado (en el peor de los casos) en redes ideales a la versión de búsqueda de anillo-LWE, donde el objetivo es recuperar el secreto (con alta probabilidad, para cualquier ) a partir de una cantidad arbitraria de productos ruidosos". ${\displaystyle \mathbf {R} }$ ${\displaystyle s\in \mathbf {R} _{q}}$ ${\displaystyle s}$^[1]

En esa cita, El anillo es y el anillo es . ${\displaystyle \mathbf {R} }$ ${\displaystyle \mathbf {Z} [x]/\Phi (x)}$ ${\displaystyle \mathbf {R} _{q}}$ ${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$

Se sabe que el α-SVP en redes regulares es NP-duro gracias al trabajo de Daniele Micciancio en 2001, aunque no para los valores de α requeridos para un problema de reducción a aprendizaje general con errores. ^[5] Sin embargo, todavía no hay una prueba que demuestre que la dificultad del α-SVP para redes ideales sea equivalente al α-SVP promedio. Más bien, tenemos una prueba de que si hay instancias de α-SVP que son difíciles de resolver en redes ideales, entonces el problema RLWE será difícil en instancias aleatorias. ^[1]

En relación con la dificultad de los problemas de vectores más cortos en redes ideales, el investigador Michael Schneider escribe: "Hasta ahora no existe ningún algoritmo SVP que haga uso de la estructura especial de las redes ideales. Se cree ampliamente que resolver SVP (y todos los demás problemas de redes) en redes ideales es tan difícil como en redes regulares". ^[6] La dificultad de estos problemas en redes regulares es demostrablemente NP-hard . ^[5] Sin embargo, hay una minoría de investigadores que no creen que las redes ideales compartan las mismas propiedades de seguridad que las redes regulares. ^[7]

Peikert cree que estas equivalencias de seguridad hacen del problema RLWE una buena base para la criptografía futura. Escribe: "Existe una prueba matemática de que la única forma de romper el criptosistema (dentro de algún modelo de ataque formal) en sus instancias aleatorias es ser capaz de resolver el problema de red subyacente en el peor de los casos" (énfasis en el original). ^[8]

Criptografía RLWE

Una ventaja importante que tiene la criptografía basada en RLWE sobre la criptografía original basada en aprendizaje con errores (LWE) se encuentra en el tamaño de las claves públicas y privadas. Las claves RLWE son aproximadamente la raíz cuadrada de las claves en LWE. ^[1] Para 128 bits de seguridad , un algoritmo criptográfico RLWE utilizaría claves públicas de alrededor de 7000 bits de longitud. ^[9] El esquema LWE correspondiente requeriría claves públicas de 49 millones de bits para el mismo nivel de seguridad. ^{[1] [ verificación fallida ]} Por otro lado, las claves RLWE son más grandes que los tamaños de claves para los algoritmos de clave pública utilizados actualmente como RSA y Diffie-Hellman de curva elíptica que requieren tamaños de clave pública de 3072 bits y 256 bits, respectivamente, para lograr un nivel de seguridad de 128 bits. Sin embargo, desde un punto de vista computacional, se ha demostrado que los algoritmos RLWE son iguales o mejores que los sistemas de clave pública existentes. ^[10]

Existen tres grupos de algoritmos criptográficos RLWE:

Aprendizaje en anillo con intercambio de claves erróneas (RLWE-KEX)

La idea fundamental de utilizar LWE y Ring LWE para el intercambio de claves fue propuesta y presentada en la Universidad de Cincinnati en 2011 por Jintai Ding. La idea básica proviene de la asociatividad de las multiplicaciones de matrices, y los errores se utilizan para proporcionar seguridad. El artículo ^[11] apareció en 2012 después de que se presentara una solicitud de patente provisional en 2012.

En 2014, Peikert ^[12] presentó un esquema de transporte de claves que seguía la misma idea básica de Ding, donde también se utiliza la nueva idea de enviar una señal adicional de 1 bit para el redondeo en la construcción de Ding. Posteriormente, Zhang et al. publicaron una versión RLWE de la variante MQV clásica de un intercambio de claves Diffie-Hellman. ^[13] La seguridad de ambos intercambios de claves está directamente relacionada con el problema de encontrar vectores cortos aproximados en una red ideal.

Aprendizaje de anillos con firma de errores (RLWE-SIG)

En 2011, Lyubashevsky creó una versión RLWE del protocolo clásico de identificación Feige-Fiat-Shamir y la convirtió en una firma digital. ^[14] En 2012, Gunesyu, Lyubashevsky y Popplemann ampliaron los detalles de esta firma y los publicaron en su artículo "Criptografía práctica basada en red: un esquema de firma para sistemas integrados". ^[15] Estos artículos sentaron las bases para una variedad de algoritmos de firma recientes, algunos basados ​​directamente en el problema del aprendizaje en anillo con errores y otros que no están vinculados a los mismos problemas RLWE complejos. ^[16]

Aprendizaje de anillos con errores de cifrado homomórfico (RLWE-HOM)

El propósito del cifrado homomórfico es permitir que los cálculos sobre datos sensibles se realicen en dispositivos informáticos a los que no se les debe confiar los datos. Estos dispositivos informáticos pueden procesar el texto cifrado que se obtiene a partir de un cifrado homomórfico. En 2011, Brakersky y Vaikuntanathan publicaron "Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages" (Cifrado totalmente homomórfico a partir de Ring-LWE y seguridad para mensajes dependientes de claves), que construye un esquema de cifrado homomórfico directamente sobre el problema RLWE. ^[17]

Referencias

1. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2012). "Sobre redes ideales y aprendizaje con errores sobre anillos". Archivo de ePrints de criptología .
2. Peikert, Chris (2014). "Criptografía en red para Internet". En Mosca, Michele (ed.). Criptografía postcuántica . Notas de clase en informática. Vol. 8772. Springer International Publishing. págs. 197–219. CiteSeerX 10.1.1.800.4743 . doi :10.1007/978-3-319-11659-4_12. ISBN .  978-3-319-11658-7.S2CID8123895  .​
3. Shor, Peter (20 de noviembre de 1994). Algoritmos para computación cuántica: logaritmos discretos y factorización . 35.° Simposio anual sobre fundamentos de la informática. Santa Fe: IEEE. doi :10.1109/SFCS.1994.365700. ISBN 0-8186-6580-7En este artículo se presentan algoritmos de Las Vegas para hallar logaritmos discretos y factorizar números enteros en una computadora cuántica que requieren una cantidad de pasos que es polinómica en el tamaño de entrada, por ejemplo, la cantidad de dígitos del número entero que se va a factorizar. Estos dos problemas se consideran generalmente difíciles en una computadora clásica y se han utilizado como base de varios criptosistemas propuestos.
4. Dwarakanath, Nagarjun C.; Galbraith, Steven D. (18 de marzo de 2014). "Muestreo de gaussianas discretas para criptografía basada en red en un dispositivo restringido". Álgebra aplicable en ingeniería, comunicación y computación . 25 (3): 159–180. CiteSeerX 10.1.1.716.376 . doi :10.1007/s00200-014-0218-3. ISSN  0938-1279. S2CID  13718364. 
5. Micciancio, D. (1 de enero de 2001). "El vector más corto en una red es difícil de aproximar dentro de alguna constante". Revista SIAM de Computación . 30 (6): 2008–2035. CiteSeerX 10.1.1.93.6646 . doi :10.1137/S0097539700373039. ISSN  0097-5397. 
6. Schneider, Michael (2011). "Tamizaje de vectores más cortos en redes ideales". Archivo de ePrints de criptología .
7. "cr.yp.to: 2014.02.13: Un ataque de logaritmo de subcampo contra redes ideales". blog.cr.yp.to . Consultado el 2015-07-03 .
8. "¿Qué significa la "historia de advertencia" del GCHQ para la criptografía en red?". www.eecs.umich.edu . Archivado desde el original el 17 de marzo de 2016 . Consultado el 5 de enero de 2016 .
9. Singh, Vikram (2015). "Un intercambio práctico de claves para Internet mediante criptografía en red". Archivo de ePrints de criptología .
10. Verbauwhede, Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid (2014). "Implementación de software eficiente del cifrado Ring-LWE". Archivo ePrint de criptología .{{cite journal}}: CS1 maint: varios nombres: lista de autores ( enlace )
11. Ding, Jintai; Xie, Xiang; Lin, Xiaodong (1 de enero de 2012). "Un esquema de intercambio de claves simple y demostrablemente seguro basado en el problema del aprendizaje con errores". Archivo de ePrints de criptología .
12. Peikert, Chris (1 de enero de 2014). "Criptografía en red para Internet". Archivo de ePrints de criptología .
13. Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Snook, Michael; Dagdelen, Özgür (2014). "Intercambio de claves autenticado a partir de redes ideales". Archivo de ePrints de criptología .
14. Lyubashevsky, Vadim (2011). "Firmas de red sin trampillas". Archivo de ePrints de criptología .
15. Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). Prouff, Emmanuel; Schaumont, Patrick (eds.). Criptografía práctica basada en red: un esquema de firma para sistemas integrados . Apuntes de clase en informática. Springer Berlin Heidelberg. págs. 530–547. doi :10.1007/978-3-642-33027-8_31. ISBN . 978-3-642-33026-1.
16. "BLISS Signature Scheme" (Esquema de firmas BLISS). bliss.di.ens.fr . Consultado el 4 de julio de 2015 .
17. Brakerski, Zvika; Vaikuntanathan, Vinod (2011). Rogaway, Phillip (ed.). Cifrado totalmente homomórfico de Ring-LWE y seguridad para mensajes dependientes de clave . Notas de clase en informática. Springer Berlin Heidelberg. págs. 505–524. doi :10.1007/978-3-642-22792-9_29. ISBN . 978-3-642-22791-2.