Aprendizaje en anillo con errores.

Problema computacional posiblemente útil para la criptografía poscuántica

En la criptografía poscuántica , el aprendizaje en anillo con errores ( RLWE ) es un problema computacional que sirve como base para 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 que 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 pueden 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 de texto cifrado, como la aritmética de valores numéricos almacenados en una base de datos cifrada.

RLWE se denomina más propiamente aprendizaje con errores sobre anillos y es simplemente el problema más amplio de aprendizaje con errores (LWE) especializado en anillos polinomiales sobre campos finitos. ^[1] Debido a la supuesta 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, así como la factorización de enteros y el problema de logaritmos discretos han servido como base para criptografía de clave pública desde principios de los años 1980. ^[2] Una característica importante de basar la criptografía en el problema del aprendizaje en anillo con errores 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 (una reducción de tiempo polinómico). desde este problema SVP hasta el problema RLWE se ha presentado ^[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 al azar. 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 números primos de 384 bits, pero no al producto de dos números primos de 512 bits. La factorización de enteros constituye la base del algoritmo criptográfico RSA, ampliamente utilizado.

El problema del aprendizaje en anillo con errores (RLWE) se basa en la aritmética de polinomios con coeficientes de un cuerpo 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 campo finito, generalmente el campo de un número entero primo . El conjunto de polinomios sobre un cuerpo finito con las operaciones de suma y multiplicación forma un anillo polinomial infinito ( ). El contexto RLWE funciona con un anillo de cociente finito de este anillo infinito. El anillo de cociente suele ser el anillo de cociente finito (factor) formado al reducir todos los polinomios en módulo de un polinomio irreducible . Este anillo de cociente finito se puede escribir como lo hacen muchos autores . ^[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 cociente 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 para el 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 infinita (también llamada norma uniforme ). La norma infinita de un polinomio es simplemente el coeficiente más grande del polinomio cuando estos coeficientes se consideran números enteros. Por tanto, afirma que la norma infinita del polinomio es . Por tanto , el mayor coeficiente de . ${\displaystyle ||a(x)||_{\infty }=b}$ ${\displaystyle a(x)}$ ${\displaystyle b}$ ${\displaystyle b}$ ${\displaystyle a(x)}$

El último concepto necesario para comprender el problema RLWE es la generación de polinomios aleatorios 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 que sea muy probable que haya coeficientes pequeños. Cuando es un número entero primo, hay dos formas comunes de hacerlo: ${\displaystyle \mathbf {F} _{q}}$ ${\displaystyle q}$

1. Uso de muestreo uniforme: los coeficientes del polinomio pequeño se muestrean uniformemente a partir de un conjunto de coeficientes pequeños. Sea un número entero que sea mucho menor que . Si elegimos aleatoriamente coeficientes del conjunto: el polinomio será pequeño con respecto a la cota ( ). ${\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 muestreo del conjunto de acuerdo con 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 probar la seguridad del algoritmo. El artículo "Muestreo de gaussianos discretos para criptografía basada en celosía 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 RLWE

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

• ${\displaystyle a_{i}(x)}$ser 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)}$ser 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)}$ser 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 o se generaron aleatoriamente con coeficientes de todos . ${\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 campo ( ) y el límite de pequeñez ( ). En muchos algoritmos de clave pública basados ​​en RLWE, la clave privada será un par de pequeños polinomios y . La clave pública correspondiente será un par de polinomios , seleccionados aleatoriamente , y el polinomio . Dado 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 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 α multiplicado por 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 SVP aproximado (en el peor de los casos) en redes ideales a la versión de búsqueda de ring-LWE, donde el objetivo es recuperar el secreto (con alta probabilidad, para cualquiera ) de muchos arbitrariamente 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 debido al trabajo de Daniele Micciancio en 2001, aunque no para los valores de α necesarios para una reducción al problema general de aprendizaje con errores. ^[5] Sin embargo, aún no hay pruebas que demuestren que la dificultad de la α-SVP para redes ideales sea equivalente a la α-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]

Respecto a 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 Las celosías son tan duras como las celosías normales." ^[6] La dificultad de estos problemas en redes regulares es demostrablemente NP-difícil . ^[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 normales. ^[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 manera de romper el criptosistema (dentro de algún modelo de ataque formal) en sus instancias aleatorias es siendo capaz de resolver el problema de la 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 basada en aprendizaje con errores (LWE) original 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 clave para los algoritmos de clave pública utilizados actualmente como RSA y Elliptic Curve Diffie-Hellman, 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 intercambios de claves con errores (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 clave siguiendo 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 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 en anillo con firma de errores (RLWE-SIG)

Lyubashevsky creó y convirtió en una firma digital en 2011 una versión RLWE del clásico protocolo de identificación Feige-Fiat-Shamir . ^[14] Los detalles de esta firma fueron ampliados en 2012 por Gunesyu, Lyubashevsky y Popplemann en 2012 y publicados en su artículo "Practical Lattice Based Cryptography - A Signature Scheme for Embedded Systems". ^[15] Estos artículos sentaron las bases para una variedad de algoritmos de firma recientes, algunos basados ​​directamente en el problema de aprendizaje en anillo con errores y otros que no están vinculados a los mismos problemas difíciles de RLWE. ^[dieciséis]

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

El propósito del cifrado homomórfico es permitir que los cálculos de datos confidenciales 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 genera a partir de un cifrado homomórfico. En 2011, Brakersky y Vaikuntanathan publicaron "Cifrado totalmente homomórfico 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 celosías ideales y aprendizaje con errores sobre anillos". Archivo ePrint de criptología .
2. Peikert, Chris (2014). "Criptografía de celosía para Internet". En Mosca, Michele (ed.). Criptografía poscuántica . Apuntes de conferencias sobre informática. vol. 8772. Publicación internacional Springer. 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. S2CID  8123895.
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-7. Este artículo proporciona algoritmos de Las Vegas para encontrar logaritmos discretos y factorizar números enteros en una computadora cuántica que requiere un número de pasos que es polinómico en el tamaño de entrada, por ejemplo, el número de dígitos del número entero a factorizar. Estos dos problemas generalmente se consideran difíciles en una computadora clásica y se han utilizado como base para varios criptosistemas propuestos.
4. Dwarakanath, Nagarjun C.; Galbraith, Steven D. (18 de marzo de 2014). "Muestreo de gaussianos discretos para criptografía basada en celosía en un dispositivo restringido". Álgebra Aplicable en Ingeniería, Comunicaciones 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). "Es difícil aproximar el vector más corto en una red 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). "Tamizado de vectores más cortos en redes ideales". Archivo ePrint 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 3 de julio de 2015 .
8. "¿Qué significa la" advertencia "del GCHQ para la criptografía reticular?". 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 de claves práctico para Internet utilizando criptografía Lattice". Archivo ePrint 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}}: Mantenimiento CS1: 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 ePrint de criptología .
12. Peikert, Chris (1 de enero de 2014). "Criptografía de celosía para Internet". Archivo ePrint de criptología .
13. Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Róbalo, Michael; Dagdelen, Özgür (2014). "Intercambio de claves autenticado de Ideal Lattices". Archivo ePrint de criptología .
14. Lyubashevsky, Vadim (2011). "Firmas de celosía sin trampillas". Archivo ePrint de criptología .
15. Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). Prouff, Emmanuel; Schaumont, Patrick (eds.). Criptografía práctica basada en celosía: un esquema de firma para sistemas integrados . Apuntes de conferencias sobre informática. Springer Berlín Heidelberg. págs. 530–547. doi :10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1.
16. "Esquema de firma 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 claves" . Apuntes de conferencias sobre informática. Springer Berlín Heidelberg. págs. 505–524. doi :10.1007/978-3-642-22792-9_29. ISBN 978-3-642-22791-2.