El aprendizaje en anillo 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 computadoras cuánticas y también para proporcionar la base para el cifrado homomórfico . Criptografía de clave públicase 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 están en riesgo de ataque si alguna vez se pueden construir computadoras cuánticas 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 correctamente Aprendizaje con errores sobre anillos y es simplemente el problema más grande de aprendizaje con errores (LWE) especializado en anillos polinomiales sobre campos finitos. [1] Debido a la presunta dificultad de resolver el problema de 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, al igual que la factorización de enteros y el problema del logaritmo discreto han servido como base para 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 del aprendizaje en anillo con errores es el hecho de que la solución al problema RLWE se puede utilizar para resolver el problema del vector más corto (SVP) NP-hard en una red (una reducción del tiempo polinomial desde el problema de SVP al problema de 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 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 el producto de dos primos de 512 bits. La factorización de enteros forma la base del algoritmo criptográfico RSA ampliamente utilizado .
El problema de aprendizaje en anillo 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:
Los polinomios se pueden agregar y multiplicar de la manera habitual. En el contexto RLWE, los coeficientes de los polinomios y todas las operaciones que involucren esos coeficientes se realizarán en un campo finito, típicamente el campo para un número entero primo . El conjunto de polinomios sobre un campo finito con las operaciones de suma y multiplicación forma un anillo polinomial infinito (). El contexto RLWE trabaja con un anillo de cociente finito de este anillo infinito. El anillo del cociente es típicamente el anillo del cociente finito (factor) formado al reducir todos los polinomios enmódulo un polinomio irreducible . Este anillo de cociente finito se puede escribir como aunque muchos autores escriben . [1]
Si el grado del polinomio es , el subanillo se convierte en el anillo de polinomios de grado menor que modulo con coeficientes de . Los valores, , junto con el polinomio definir parcialmente el contexto matemático para el problema RLWE.
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 de infinito de un polinomio es simplemente el coeficiente más grande del polinomio cuando estos coeficientes se ven como números enteros. Por eso, establece que la norma infinita del polinomio es . Por lo tanto es el mayor coeficiente de .
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 el coeficientes del polinomio de , dónde se representa típicamente como el conjunto .
La generación aleatoria de un polinomio "pequeño" se realiza generando los coeficientes del polinomio a partir de de una manera que garantice o haga muy probablemente pequeños coeficientes. Hay dos formas habituales de hacer esto:
- Uso de muestreo uniforme: los coeficientes del polinomio pequeño se muestrean uniformemente a partir de un conjunto de coeficientes pequeños. Dejar ser un número entero que sea mucho menor que . Si elegimos aleatoriamente coeficientes del conjunto: el polinomio será pequeño con respecto al límite ().
- Uso de muestreo gaussiano discreto : para un valor impar de, los coeficientes del polinomio se eligen aleatoriamente mediante 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 documento "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]
El problema RLWE
El problema de RLWE se puede plantear de dos formas diferentes: una versión de "búsqueda" y una versión de "decisión". Ambos comienzan con la misma construcción. Dejar
- ser un conjunto de polinomios aleatorios pero conocidos de con coeficientes de todos .
- ser un conjunto de pequeños polinomios aleatorios y desconocidos relativos a un límite en el ring .
- ser un pequeño polinomio desconocido relativo a un límite en el ring .
- .
La versión de búsqueda implica encontrar el polinomio desconocido dada la lista de pares de polinomios .
La versión de Decisión del problema se puede establecer de la siguiente manera. Dada una lista de pares de polinomios, determine si el Los polinomios se construyeron como o se generaron aleatoriamente a partir de con coeficientes de todos .
La dificultad de este problema está parametrizada por la elección del polinomio del cociente (), su grado (), el campo (), y el límite de la 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, seleccionado al azar de y el polinomio . Dado y , debería ser computacionalmente inviable recuperar el polinomio .
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 por elementos derepresentados como vectores enteros. [1] Este problema se conoce comúnmente como 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:
- "... damos una reducción cuántica de SVP aproximada (en el peor de los casos) en redes ideales en a la versión de búsqueda de ring-LWE, donde el objetivo es recuperar el secreto (con alta probabilidad, para cualquier ) de muchos productos ruidosos arbitrariamente ". [1]
En esa cita, el anillo es y el anillo es .
Se sabe que el α-SVP en celosías regulares es NP-hard debido al trabajo de Daniele Micciancio en 2001, aunque no para los valores de α requeridos para una reducción al problema de aprendizaje general con errores. [5] Sin embargo, todavía no hay una prueba que demuestre que la dificultad del α-SVP para las celosías ideales sea equivalente al α-SVP promedio. Más bien tenemos una prueba de que si hay algún casos α-SVP que son difíciles de resolver en celosías ideales entonces el problema RLWE será difícil en casos aleatorios. [1]
Con respecto a la dificultad de los problemas de vectores más cortos en celosías ideales, el investigador Michael Schneider escribe: "Hasta ahora no existe un algoritmo SVP que haga uso de la estructura especial de las celosías ideales. Se cree ampliamente que resolver SVP (y todos los demás problemas de celosía) en condiciones ideales celosías es tan duro como en celosías regulares ". [6] La dificultad de estos problemas en celosías regulares es probablemente NP-hard . [5] Sin embargo, hay una minoría de investigadores que no cree que las celosías ideales compartan las mismas propiedades de seguridad que las celosías regulares. [7]
Peikert cree que estas equivalencias de seguridad hacen del problema RLWE una buena base para la criptografía futura. Escribe: "Hay 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 resolviendo el problema de la red subyacente en el peor de los casos" (énfasis en el original). [8]
Criptografía RLWE
Una gran ventaja que tiene la criptografía basada en RLWE sobre la criptografía basada en aprendizaje original 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 usarí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 las claves de 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 intercambio de claves de errores (RLWE-KEX)
La idea fundamental de utilizar LWE y Ring LWE para el intercambio de claves fue propuesta y archivada 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 la seguridad. El documento [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 siguiendo la misma idea básica de Ding, donde también se utiliza la nueva idea de enviar una señal de 1 bit adicional para redondear en la construcción de Ding. Posteriormente, Zhang et al. Publicaron una versión RLWE de la variante clásica MQV 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ó una versión RLWE del clásico protocolo de identificación Feige-Fiat-Shamir y la convirtió en una firma digital en 2011. [14] Los detalles de esta firma fueron extendidos 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 de RLWE. [dieciséis]
Aprendizaje de anillo con errores de cifrado homomórfico (RLWE-HOM)
El propósito del cifrado homomórfico es permitir que los cálculos sobre 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
- ^ a b c d e f g h i Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2012). "Sobre celosías ideales y aprendizaje con errores sobre anillos" . Cite journal requiere
|journal=
( ayuda ) - ^ Peikert, Chris (2014). "Criptografía de celosía para Internet". En Mosca, Michele (ed.). Criptografía post-cuántica . Apuntes de conferencias en informática. 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.
- ^ Shor, Peter (20 de noviembre de 1994). Algoritmos de cálculo cuántico: 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 toma una serie de pasos que son polinomiales 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 de varios criptosistemas propuestos.
- ^ 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, Comunicación y Computación . 25 (3): 159–180. doi : 10.1007 / s00200-014-0218-3 . ISSN 0938-1279 . S2CID 13718364 .
- ^ a b Micciancio, D. (1 de enero de 2001). "El vector más corto en una celosía 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 .
- ^ Schneider, Michael (2011). "Tamizado de vectores más cortos en celosías ideales" . Cite journal requiere
|journal=
( ayuda ) - ^ "cr.yp.to: 2014.02.13: un ataque de logaritmo de subcampo contra celosías ideales" . blog.cr.yp.to . Consultado el 3 de julio de 2015 .
- ^ "¿Qué significa la" advertencia "de GCHQ para la criptografía de celosía?" . www.eecs.umich.edu . Archivado desde el original el 17 de marzo de 2016 . Consultado el 5 de enero de 2016 .
- ^ Singh, Vikram (2015). "Un intercambio de claves práctico para Internet utilizando criptografía de celosía" . Cite journal requiere
|journal=
( ayuda ) - ^ Verbauwhede, Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid (2014). "Implementación de software eficiente de cifrado Ring-LWE" . Cite journal requiere
|journal=
( ayuda ) - ^ Ding, Jintai; Xie, Xiang; Lin, Xiaodong (1 de enero de 2012). "Un esquema de intercambio de claves seguro y demostrable basado en el problema de aprendizaje con errores" . Cite journal requiere
|journal=
( ayuda ) - ^ Peikert, Chris (1 de enero de 2014). "Criptografía de celosía para Internet" . Cite journal requiere
|journal=
( ayuda ) - ^ Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Snook, Michael; Dagdelen, Özgür (2014). "Intercambio de claves autenticadas de Ideal Lattices" . Cite journal requiere
|journal=
( ayuda ) - ^ Lyubashevsky, Vadim (2011). "Firmas de celosía sin trampillas" . Cite journal requiere
|journal=
( ayuda ) - ^ 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 en 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.
- ^ "Esquema de firma BLISS" . bliss.di.ens.fr . Consultado el 4 de julio de 2015 .
- ^ 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 en 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.