Aprendizaje en anillo con errores

En criptografía postcuántica , el aprendizaje de anillos con errores ( RLWE ) es un problema computacional que sirve de base para nuevos algoritmos criptográficos , como NewHope , diseñados para proteger contra el criptoanálisis mediante computadoras cuánticas y también para proporcionar la base del cifrado homomórfico . La criptografía de clave pública se basa en la construcción de problemas matemáticos que se consideran difíciles de resolver si no se dispone de información adicional, pero que son fáciles de resolver si se conoce alguna información utilizada en su construcción. Algunos problemas de este tipo que se utilizan actualmente en criptografía corren el riesgo de ser atacados si se logran construir computadoras cuánticas suficientemente grandes, por lo que se buscan problemas resistentes.

RLWE se denomina más propiamente aprendizaje con errores sobre anillos y es simplemente el problema de aprendizaje con errores (LWE) más grande especializado a anillos polinomiales sobre cuerpos 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, al igual que 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 de anillos 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 un retículo (se ha presentado una reducción en 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 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 la factorización de enteros . Se cree que es computacionalmente intratable factorizar el producto de dos números primos si estos son suficientemente grandes y se eligen al azar. ^{[ 3 ]} Hasta 2015, la investigación había llevado a la factorización del producto de dos primos de 384 bits, pero no del producto de dos primos de 512 bits. La factorización de enteros constituye la base del algoritmo criptográfico RSA , ampliamente utilizado.

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

${\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 de 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${\textstyle \mathbf {Z} /q\mathbf {Z} =\mathbf {F} _{q}}$para un número primo entero${\textstyle q}$. El conjunto de polinomios sobre un cuerpo finito con las operaciones de suma y multiplicación forma un anillo de polinomios infinito (${\textstyle \mathbf {F} _{q}[x]}$). El contexto RLWE trabaja con un anillo cociente finito de este anillo infinito. El anillo cociente es típicamente el anillo cociente finito (factor) formado al reducir todos los polinomios en${\textstyle \mathbf {F} _{q}[x]}$módulo un polinomio irreducible${\textstyle \Phi (x)}$Este anillo cociente finito se puede escribir como${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$aunque muchos autores escriben${\displaystyle \mathbf {Z} _{q}[x]/\Phi (x)}$. ^{[ 1 ]}

Si el grado del polinomio${\displaystyle \Phi (x)}$es${\textstyle n}$, el anillo cociente se convierte en el anillo de polinomios de grado menor que${\displaystyle n}$módulo${\displaystyle \Phi (x)}$con coeficientes de${\displaystyle F_{q}}$. Los valores${\textstyle n}$,${\textstyle q}$, junto con el polinomio${\displaystyle \Phi (x)}$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 infinito (también llamada norma uniforme ). La norma infinito de un polinomio es simplemente el coeficiente más grande del polinomio cuando estos coeficientes se consideran enteros. Por lo tanto,${\displaystyle ||a(x)||_{\infty }=b}$establece que la norma infinito del polinomio${\displaystyle a(x)}$es${\displaystyle b}$. De este modo${\displaystyle b}$es el coeficiente más grande de${\displaystyle a(x)}$.

El concepto final necesario para comprender el problema RLWE es la generación de polinomios aleatorios en${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$y la generación de polinomios "pequeños". Un polinomio aleatorio se genera fácilmente simplemente muestreando aleatoriamente el${\displaystyle n}$coeficientes del polinomio de${\displaystyle \mathbf {F} _{q}}$, dónde${\displaystyle \mathbf {F} _{q}}$se representa típicamente como el conjunto${\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 a partir de${\displaystyle \mathbf {F} _{q}}$de una manera que garantice coeficientes pequeños o los haga muy probables. Cuando${\displaystyle q}$Si es un número primo, existen dos formas comunes de hacerlo:

1. Utilizando muestreo uniforme: los coeficientes del polinomio pequeño se muestrean uniformemente a partir de un conjunto de coeficientes pequeños. Sea${\textstyle b}$ser un número entero que sea mucho menor que${\textstyle q}$Si elegimos aleatoriamente coeficientes del conjunto:${\textstyle \{-b,-b+1,-b+2,\ldots ,-2,-1,0,1,2,\ldots ,b-2,b-1,b\}}$el polinomio será pequeño con respecto al límite (${\textstyle b}$).
2. Utilizando muestreo gaussiano discreto – Para un valor impar de${\textstyle q}$, los coeficientes del polinomio se eligen aleatoriamente mediante muestreo del conjunto${\textstyle \{-(q-1)/2,\ldots ,(q-1)/2\}}$según una distribución gaussiana discreta con media${\displaystyle 0}$y parámetro de distribución${\textstyle \sigma }$Las referencias describen con todo detalle cómo se puede lograr esto. Es más complicado que el muestreo uniforme, pero permite demostrar la seguridad del algoritmo. El artículo "Sampling from Discrete Gaussians for Lattice-Based Cryptography on a Constrained Device" de Dwarakanath y Galbraith ofrece una visión general de este problema. ^{[ 4 ]}

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

• ${\displaystyle a_{i}(x)}$sea ​​un conjunto de polinomios aleatorios pero conocidos de${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$con coeficientes de todos${\displaystyle \mathbf {F} _{q}}$.
• ${\displaystyle e_{i}(x)}$sea ​​un conjunto de polinomios pequeños, aleatorios y desconocidos con respecto a un límite.${\displaystyle b}$en el ring${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$.
• ${\displaystyle s(x)}$sea ​​un pequeño polinomio desconocido en relación con un límite${\displaystyle b}$en el ring${\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.${\displaystyle s(x)}$dada la lista de pares de polinomios${\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${\displaystyle (a_{i}(x),b_{i}(x))}$determinar si el${\displaystyle b_{i}(x)}$Los polinomios se construyeron como${\displaystyle b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)}$o se generaron aleatoriamente a partir de${\displaystyle \mathbf {F} _{q}[x]/\Phi (x)}$con coeficientes de todos${\displaystyle \mathbf {F} _{q}}$.

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

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${\displaystyle \mathbf {Z} [x]/\Phi (x)}$representados como vectores enteros. ^{[ 1 ]} Este problema se conoce comúnmente como el Problema del Vector Más Corto Aproximado (α-SVP) y consiste en encontrar un vector más corto que α veces el vector más corto. Los autores de la demostración de esta equivalencia escriben:

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

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

Se sabe que el α-SVP en retículos regulares es NP-difícil 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 una prueba que demuestre que la dificultad del α-SVP para retículos ideales sea equivalente a la del α-SVP promedio. Más bien, tenemos una prueba de que si hay alguna instancia de α-SVP que sea difícil de resolver en retículos 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 retículos ideales, el investigador Michael Schneider escribe: «Hasta ahora no existe ningún algoritmo SVP que utilice la estructura especial de los retículos ideales. Se cree ampliamente que resolver SVP (y todos los demás problemas de retículos) en retículos ideales es tan difícil como en retículos regulares». ^{[ 6 ]} La dificultad de estos problemas en retículos regulares es demostrablemente NP-difícil . ^{[ 5 ]} Sin embargo, hay una minoría de investigadores que no creen que los retículos ideales compartan las mismas propiedades de seguridad que los retículos 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 siendo capaz de resolver el problema de retículo subyacente en el peor de los casos» (énfasis en el original). ^{[ 8 ]}

Una ventaja importante de la criptografía basada en RLWE sobre la criptografía original basada en aprendizaje con errores (LWE) reside 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 ]} Por otro lado, las claves RLWE son mayores que los tamaños de clave de los algoritmos de clave pública actualmente utilizados, 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: