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] ).
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:
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]
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.
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 .
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 .
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:
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
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 como o se generaron aleatoriamente a partir de con coeficientes de todos los .
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 .
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:
En esa cita, El anillo es y el anillo es .
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]
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:
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.
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]
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]
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.
{{cite journal}}
: CS1 maint: varios nombres: lista de autores ( enlace )