Entrenamiento con errores en el ring

El aprendizaje en anillo con errores (RLWE) es un problema computacional que se ha formulado como una variante del problema más general de aprendizaje con errores (LWE) para aprovechar la estructura algebraica adicional (es decir, anillos polinómicos ) de la teoría de la red [1] , que hizo posible aumentar y ampliar las capacidades de encriptación de aquellas aplicaciones criptográficas que antes estaban basadas en LWE. El problema RLWE se ha convertido en la base de nuevos algoritmos criptográficos diseñados para proteger los datos del criptoanálisis por parte de las computadoras cuánticas , así como en una importante aplicación para la construcción de esquemas de cifrado homomórfico .. Debido al hecho de que la dificultad percibida de resolver el problema RLWE es muy alta incluso en una computadora cuántica, la criptografía basada en ella puede convertirse en la criptografía de clave pública fundamental en el futuro, al igual que los problemas de factorización de números enteros y logaritmos discretos sirvieron como base. base para la criptografía de clave pública en los comienzos. Década de 1980 [2] . Cabe señalar que RLWE se puede aproximar mediante el problema de encontrar el vector más corto en redes ideales , que son redes estructuradas matemáticamente que corresponden a ideales en un anillo.

Antecedentes

Durante la última década , la criptografía de celosía ha recibido mucha atención como base para la criptografía futura y se ha convertido en un campo de rápido desarrollo. Las primitivas criptográficas basadas en las redes mencionadas anteriormente son atractivas porque su seguridad radica en la peor complejidad computacional y es probable que presenten un problema de cálculo incluso para las computadoras cuánticas.

En la actualidad, la seguridad de la criptografía moderna, en particular la criptografía de clave pública, se basa en la supuesta imposibilidad de resolver algunos problemas computacionales teóricos, como el problema de factorizar dos números enteros elegidos o calcular el logaritmo discreto para proporcionar firmas digitales, intercambio de claves y privacidad. Con tamaños de clave suficientemente grandes, estos sistemas criptográficos de clave pública se consideran virtualmente invulnerables a la piratería en computadoras modernas, supercomputadoras o grupos informáticos especiales. En 1994, Peter Shor propuso un algoritmo cuántico [3] para la factorización de números enteros antes mencionada. Su versión modificada es capaz de resolver el problema del logaritmo discreto en el grupo de puntos de la curva elíptica (ECDLP). El algoritmo en sí no se puede usar en computadoras clásicas, solo en las cuánticas, para resolver el problema de factorización o logaritmo discreto en tiempo polinomial, y dado que el concepto de computadoras cuánticas ha comenzado a desarrollarse rápidamente en este momento, se ha vuelto extremadamente importante usar algoritmos cuánticos eficientes con una clave de cifrado pública.

Descripción del algoritmo

Ring Error Learning (RLWE) se basa en la aritmética polinomial con coeficientes de campos finitos [1] . El polinomio a(x) se expresa de la siguiente manera:

a(x) = un 0 + un 1 x + un 2 x 2 + … + un n-3 x n-3 + un n-2 x n-2 + un n-1 x n-1

Para polinomios, la operación de multiplicación y suma se define como para los números ordinarios. En el contexto del problema RLWE, los coeficientes de los polinomios y todas las operaciones sobre ellos se realizarán en un campo finito definido como un número primo . El conjunto de polinomios sobre un cuerpo finito con las operaciones de suma y multiplicación forma un anillo polinomial infinito ( ), con un subanillo finito del cual funciona el problema RLWE. Por lo general, este subanillo es un anillo cociente formado por la reducción de todos los polinomios en módulo un polinomio irreducible . Este anillo de factores finitos se puede escribir como . ${\estilo de texto \mathbf {Z} /q\mathbf {Z} =\mathbf {F} _{q))$ ${\ estilo de texto q}$ ${\estilo de texto \mathbf {F}_{q}[x]}$ ${\estilo de texto \mathbf {F}_{q}[x]}$ ${\ estilo de texto \ Phi (x)}$ $\mathbf {F}_{q}[x]/\Phi (x)$

Si el grado del polinomio es , entonces el subanillo se convierte en un anillo polinomial de grado menor que módulo con coeficientes de . Los valores de , junto con el polinomio definen parcialmente el contexto matemático para el problema RLWE. $\fi (x)$ ${\ estilo de texto n}$ $norte$ $\fi (x)$ $F_q$ ${\ estilo de texto n}$ ${\ estilo de texto q}$ $\fi (x)$

Otro concepto importante para RLWE es el concepto de polinomios "pequeños" con respecto a alguna medida. La medida usual para RLWE es la norma "infinita" . El concepto de la norma infinita de un polinomio se presenta simplemente como el mayor coeficiente de un polinomio cuando estos coeficientes se tratan como números enteros. Por lo tanto, significa que la norma infinita del polinomio es . Por lo tanto, es el coeficiente más grande . $||a(x)||_{\infty}=b$ $hacha)$ $b$ $b$ $hacha)$

El último concepto importante que debe comprender RLWE es la generación de polinomios aleatorios y la generación de polinomios "pequeños". Un polinomio aleatorio se genera fácilmente mediante una distribución aleatoria simple de los coeficientes polinómicos de , donde generalmente se representa como un conjunto . $\mathbf {Z}_{q}[x]/\Phi (x)$ $norte$ ${\ estilo de visualización \ mathbf {F} _ {q}}$ ${\ estilo de visualización \ mathbf {F} _ {q}}$ ${\displaystyle \{-(q-1)/2,...,-1,0,1,...,(q-1)/2\))$

La generación aleatoria de polinomios "pequeños" se realiza generando los coeficientes del polinomio a partir de los cuales se garantiza o al menos se hace muy probable que estos coeficientes sean pequeños. Hay dos formas comunes de hacer esto: ${\ estilo de visualización \ mathbf {F} _ {q}}$

Usando una distribución uniforme discreta : los coeficientes de un polinomio pequeño se seleccionan uniformemente de un conjunto de coeficientes pequeños. Sea un entero mucho menor que . Si seleccionamos aleatoriamente coeficientes del conjunto , entonces el polinomio será "pequeño" con respecto al valor límite ( ). ${\ estilo de texto b}$ ${\ estilo de texto q}$ ${\textstyle \{-b,-b+1,-b+2,\ldots,-2,-1,0,1,2,\ldots,b-2,b-1,b\))$ ${\ estilo de texto b}$
Usando la función gaussiana : para un valor impar, los coeficientes del polinomio se seleccionan aleatoriamente del conjunto de acuerdo con la distribución gaussiana discreta con expectativa matemática y varianza . Este método es más complicado que la distribución uniforme discreta, pero permite probar la seguridad del algoritmo [4] . ${\ estilo de texto q}$ ${\estilo de texto \{-(q-1)/2,\ldots,(q-1)/2\))$ ${\ estilo de visualización 0}$ ${\ estilo de texto \ sigma}$

Problema RLWE

La formulación del problema de aprendizaje con errores en el anillo se puede dar de dos formas diferentes: la primera opción es "buscar", la segunda opción es "solución". Ambos al principio de la construcción del algoritmo son iguales. Suponer:

${\ estilo de visualización a_ {i} (x)}$ - un conjunto de polinomios aleatorios pero conocidos de con coeficientes diferentes de todos . $\mathbf {Z}_{q}[x]/\Phi (x)$ ${\ estilo de visualización \ mathbf {F} _ {q}}$
${\ Displaystyle e_ {i} (x)}$ - un conjunto de pequeños polinomios aleatorios y desconocidos con respecto al límite en el anillo . $b$ $\mathbf {Z}_{q}[x]/\Phi (x)$
${\ estilo de visualización s (x)}$ es un pequeño polinomio desconocido con respecto a la frontera en el anillo . $b$ $\mathbf {Z}_{q}[x]/\Phi (x)$
$b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$ .

La versión de "búsqueda" del problema RLWE es encontrar un polinomio de una lista de pares de polinomios . ${\ estilo de visualización s (x)}$ ${\ estilo de visualización (a_ {i} (x), b_ {i} (x))}$

La versión de "solución" de este problema se puede formular de la siguiente manera: una lista dada de pares de polinomios determina si los polinomios se construyeron como o se generaron aleatoriamente a partir de coeficientes de todos . ${\ estilo de visualización (a_ {i} (x), b_ {i} (x))}$ ${\ Displaystyle b_ {i} (x)}$ $b_{i}(x)=(a_{i}(x)\cdot s(x))+e_{i}(x)$ $\mathbf {Z}_{q}[x]/\Phi (x)$ ${\ estilo de visualización \ mathbf {F} _ {q}}$

La complejidad de este problema radica en la elección de un polinomio factorial , cuyo grado es , sobre el campo y con pequeñez asociada . En muchos algoritmos basados en claves públicas RLWE, la clave privada será un par de polinomios "pequeños" y . Entonces la clave pública que le corresponde será un par de polinomios , elegidos al azar , y un polinomio . Los datos y polinomios deben ser computacionalmente indecidibles para el problema de recuperación de polinomios . $\fi (x)$ $norte$ ${\ estilo de visualización \ mathbf {F} _ {q}}$ $b$ ${\ estilo de visualización s (x)}$ $ex)$ $hacha)$ $\mathbf {Z}_{q}[x]/\Phi (x)$ $t(x)=(a(x)\cdot s(x))+e(x)$ $hacha)$ $t(x)$ ${\ estilo de visualización s (x)}$

Seguridad

En los casos en que el polinomio es circular , la complejidad de resolver el problema RLWE de la versión de "búsqueda" es equivalente a la complejidad de encontrar un vector corto (no necesariamente el más corto) en una red ideal que consta de elementos representados como vectores enteros [ 1] . Este problema se conoce comúnmente como el problema del vector más corto aproximado (α-ECV) y consiste en encontrar un vector que sea α veces más corto que el más corto. Se sabe que el problema α-ZKV en redes regulares tiene complejidad NP según el trabajo de Daniel Michancio en 2001, y esto no se debe a los valores de α que lo reducen a un problema general de aprendizaje con errores [5] . Sin embargo, todavía no hay pruebas que muestren que la complejidad del problema α-ZKV para redes ideales es equivalente en promedio al problema α-ZKV. Sin embargo, existe evidencia de que si un solo problema de α-ZKV es difícil de resolver en redes ideales, entonces el problema de RLWE será difícil de resolver en cualquier forma aleatoria. [una] $\fi (x)$ $\mathbf {Z} [x]/\Phi (x)$

Con respecto a la complejidad del problema de encontrar el vector más corto en los retículos ideales, el investigador Michael Schneider escribe: "Hasta ahora, no existe ningún algoritmo que use la estructura especial de los retículos ideales. Se cree ampliamente que resolver el problema del vector más corto (y otros problemas) en celosías ideales es tan difícil como y en celosías regulares". [6] Se demuestra que la complejidad de estos problemas en redes regulares es NP. [5] . Sin embargo, hay un pequeño número de partidarios de otra opinión, que creen que las celosías ideales son tan seguras como las normales. [7]

Peikert cree que esta similitud en la seguridad hace que el problema RLWE sea una buena base para la criptografía futura. Él escribe: "Hay una prueba matemática de la ' exclusividad' (dentro de algún modelo de ataque) de una forma de romper un criptosistema en sus instancias aleatorias: esta es la capacidad de resolver el problema de red correspondiente en el peor de los casos" [8]

Criptografía RLWE

La principal ventaja de la criptografía basada en el aprendizaje con errores en el anillo frente a la original (sobre el aprendizaje con errores del inglés LWE) es la longitud de las claves pública y privada. Para RLWE, es aproximadamente igual a la raíz cuadrada de la longitud de la clave en LWE [1] . Para un nivel de seguridad de 128 bits , el algoritmo RLWE utilizará una clave pública de 7000 bits. [9] El esquema LWE correspondiente es de 49 millones de bits para el mismo nivel de seguridad. [1] Por otro lado, las teclas RLWE siguen siendo más largas que las utilizadas por sus antecesores RSA y las curvas elípticas de Diffie-Hellman. que requieren claves de 3072 y 256 bits, respectivamente, para alcanzar el nivel de seguridad de 128 bits. Desde un punto de vista computacional, los algoritmos RLWE son al menos iguales o incluso mejores en rendimiento que los algoritmos de clave pública existentes. [diez]

Hay tres grupos de algoritmos criptográficos RLWE:

Intercambio de clave de aprendizaje de error (RLWE-KEX)

La idea fundamental de usar LWE y RLWE para el intercambio de claves fue propuesta y expresada en 2011 por Jintai Ding en la Universidad de Cincinnati. La idea básica es que la multiplicación de matrices es asociativa y los errores se usan por seguridad. En 2012, aparece un artículo [11] después de presentar una solicitud de patente en el mismo año.

En 2014, Peikert [12] introdujo un esquema de transporte clave siguiendo la idea básica de Dean, quien también usa una señal adicional de 1 bit para redondear en su diseño. Más tarde, Zang [13] publicó una versión RLWE del clásico intercambio de claves MQV Diffie-Hellman . La seguridad de ambos métodos de intercambio de claves está directamente relacionada con el problema de encontrar vectores cortos en una red ideal aproximadamente.

Firma de entrenamiento de error de anillo (RLWE-SIG)

La versión RLWE del clásico protocolo Feig-Fiat-Shamir fue creada y firmada digitalmente en 2011 por Lyubashevsky. [14] Los detalles de esta firma fueron revelados en 2012 por Gunes, Lyubashevsky y Poppleman y publicados en su artículo "Practical Lattice-Based Cryptography - A Signature Scheme for Embedded Systems". [15] Estos documentos sentaron las bases para muchos algoritmos modernos, algunos de los cuales se basan directamente en el problema RLWE, y algunos de los cuales no están relacionados con RLWE en absoluto. [dieciséis]

Cifrado homomórfico en el aprendizaje de errores de anillo (RLWE-HOM)

El objetivo del cifrado homomórfico es permitir que los datos confidenciales se calculen en dispositivos informáticos en los que no se debe confiar con esos datos. Estos dispositivos pueden procesar el texto cifrado a la salida del cifrado homomórfico. En 2011, Brakerski y Vaikuntanathan publicaron "Cifrado homomórfico completo para Ring-LWE y seguridad de mensajes dependientes de claves", que describe un esquema de cifrado homomórfico directamente para el problema RLWE. [17]

Ataques a RLWE

Es muy importante comprender qué tan seguro es RLWE como tal. En el trabajo de Luboshevsky [1] , se presta mucha atención a la seguridad del algoritmo, sin embargo, para resaltar estas propiedades del problema y demostrar su total cumplimiento con las declaradas, se deben realizar una serie de ataques directos a RLWE. llevado a cabo. Este problema está determinado por la elección de un campo numérico y un número primo llamado módulo, junto con una distribución de errores. Dukas y Durmus propusieron una versión no dual de RLWE en un entorno ciclotómico y demostraron que la complejidad de la versión nueva y la antigua es idéntica [18] . Esta versión de RLWE genera la distribución de errores como una función gaussiana discreta en el anillo de enteros bajo incrustación canónica, en lugar de en la imagen ideal dual. Las variantes duales y no duales son equivalentes hasta la distribución de errores [19] . Para la versión no dual de RLWE, los autores de [20] propusieron un ataque a la versión "solución" de RLWE. El ataque usa un módulo de grado de residuo de 1, lo que da un homomorfismo de anillo → . El ataque funciona cuando, con una probabilidad abrumadora, la distribución de errores RLWE en un conjunto de pares toma valores solo en un pequeño subconjunto de . Luego, los autores de [20] dan toda una familia de ejemplos que son vulnerables a los ataques. Sin embargo, los campos numéricos vulnerables no son campos de Galois, por lo que el teorema de reducir la versión de "búsqueda" a la versión de "solución" no es aplicable y el ataque no puede usarse directamente para la variante de "búsqueda" del problema RLWE, que en realidad fue el objetivo del trabajo presentado [20] . ${\ estilo de texto K}$ ${\ estilo de texto q}$ ${\ estilo de texto R}$ ${\ estilo de texto q}$ ${\ estilo de texto p: R}$ ${\ estilo de texto \ mathbf {F} _ {q))$ ${\ estilo de texto p}$ ${\ estilo de texto \ mathbf {F} _ {q))$

Sin embargo, más adelante en otro trabajo [19] , este ataque se generalizó a algunos campos y módulos de Galois de mayor grado. También presentó su implementación para instancias específicas de RLWE, incluida la opción de reducir "búsqueda" a "solución". Su principio fundamental era que el homomorfismo en el anillo se consideraba en la forma → (donde, es el grado de ) para > 1, y que la distribución de errores difería de la aleatoria, utilizando una prueba estadística de chi-cuadrado en lugar de confiar en la valores del polinomio de error. Los autores también destacan que llevaron a cabo un ataque sobre una variación de RLWE con anillos ciclotómicos simples bajo ciertas suposiciones sobre el módulo y la tasa de error, que se realiza con éxito y con una alta probabilidad. Es decir, mostraron un ataque a la versión no dual de RLWE cuando el módulo es único y primo . Además, los autores del artículo llevaron a cabo otro ataque a la versión dual RLWE de la "solución" en el -ésimo campo ciclotómico con un módulo arbitrario , asumiendo que el ancho de la distribución del error es de aproximadamente . ${\ estilo de texto R}$ ${\ estilo de texto \ mathbf {F} _ {q}^{f}}$ ${\ estilo de texto f}$ ${\ estilo de texto q}$ ${\ estilo de texto f}$ ${\ estilo de texto p}$ ${\ estilo de texto \ mathbf {Q} }$ ${\ estilo de texto p}$ ${\ estilo de texto q}$ ${\textstyle 1/{\sqrt {p}}}$

Notas

↑ 1 2 3 4 5 6 7 Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded. Sobre Redes Ideales y Aprendizaje con Errores sobre Anillos . - 2012. Archivado el 26 de noviembre de 2018.
↑ Peikert, Chris. Mosca, Michele. Criptografía de celosía para Internet . - S. 197-219 . Archivado desde el original el 9 de octubre de 2018.
↑ P. Shor. Algoritmos para Computación Cuántica : Logaritmos Discretos y Factorización .
↑ Dwarakanath y Galbraith. Muestreo de gaussianas discretas para criptografía basada en celosías en un dispositivo restringido // Álgebra aplicable en ingeniería, comunicación y computación. - 2014. - 18 de marzo ( vol. 25 ). - P. 159-180 . — ISSN 3 . Archivado desde el original el 15 de diciembre de 2018.
↑ 1 2 D. Micciancio. El vector más corto en una red es difícil de aproximar dentro de alguna constante // SIAM Journal on Computing. - 2001. - 1 de enero ( vol. 30 ). - S. 2008-2035 . — ISSN 0097-5397 . Archivado desde el original el 9 de diciembre de 2016.
↑ Schneider, Michael. Tamizado de vectores más cortos en celosías ideales : revista . — 2011.
↑ cr.yp.to: 2014.02.13: Un ataque de logaritmo de subcampo contra redes ideales . Consultado el 13 de diciembre de 2018. Archivado desde el original el 17 de mayo de 2015. (indefinido)
↑ ¿Qué significa el "cuento de advertencia" de GCHQ para la criptografía de celosía? . www.eecs.umich.edu . Consultado el 5 de enero de 2016. Archivado desde el original el 17 de marzo de 2016. (indefinido)
↑ Singh, Vikram. Un intercambio práctico de claves para Internet mediante criptografía de entramado : revista . — 2015.
↑ Verbauwhede, Ruan de Clercq, Sujoy Sinha Roy, Frederik Vercauteren, Ingrid. Implementación de software eficiente del cifrado Ring-LWE (inglés) : revista. — 2014.
↑ Ding, Jintai; Xie, Xiang; Lin, Xiaodong. Un esquema simple de intercambio de claves seguro y demostrable basado en el problema de aprendizaje con errores : diario . - 2012. - 1 de enero.
↑ Peikert, Chris. Criptografía de celosía para Internet (neopr.) . - 2014. - 1 de enero.
↑ Zhang, Jiang; Zhang, Zhenfeng; Ding, Jintai; Róbalo, Michael; Dagdelen, Ozgur. Intercambio de claves autenticadas de Ideal Lattices (inglés) : diario. — 2014.
↑ Lyubashevsky, Vadim. Firmas de celosía sin trampillas (neopr.) . — 2011.
↑ Guneysu, Tim; Lyubashevsky, Vadim; Poppelman, Thomas. Criptografía práctica basada en entramado: un esquema exclusivo para sistemas integrados / Prouff, Emmanuel; Schaumont, Patrick. - Springer Berlín Heidelberg , 2012. - Pág. 530-547. — (Apuntes de clase en informática). - ISBN 978-3-642-33026-1 .
↑ Esquema de firma BLISS (enlace descendente) . bliss.di.ens.fr . Consultado el 4 de julio de 2015. Archivado desde el original el 6 de octubre de 2015. (indefinido)
↑ Brakerski, Zvika; Vaikuntanathan, Vinod. Cifrado totalmente homomórfico de Ring-LWE y seguridad para mensajes dependientes de clave (inglés) / Rogaway, Phillip. - Springer Berlín Heidelberg , 2011. - Pág. 505-524. — (Apuntes de clase en informática). — ISBN 978-3-642-22791-2 .
↑ Ducas, L., Durmus, A. Ring-LWE en anillos polinómicos, Springer. - 2012. - S. 34-51 .
↑ 1 2 Hao Chen, Kristin Lauter, Katherine E. Stange. Ataques al problema Search-RLWE con pequeños errores . Archivado desde el original el 15 de diciembre de 2018.
↑ 1 2 3 Yara Elias, Kristin E. Lauter, Ekin Ozman, Katherine E. Stange. Instancias probablemente débiles de Ring-LWE . Archivado desde el original el 8 de junio de 2019.