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 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, así como la factorización de números 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] ).
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:
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]
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.
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 .
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 .
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:
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
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 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 .
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 .
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:
En esa cita, El anillo es y el anillo es .
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]
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:
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.
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]
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]
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.
{{cite journal}}
: Mantenimiento CS1: varios nombres: lista de autores ( enlace )