En matemáticas discretas, las redes ideales son una clase especial de redes y una generalización de redes cíclicas . [1] Las redes ideales ocurren naturalmente en muchas partes de la teoría de números , pero también en otras áreas. En particular, tienen un lugar importante en la criptografía . Micciancio definió una generalización de las redes cíclicas como redes ideales. Se pueden utilizar en criptosistemas para disminuir en una raíz cuadrada el número de parámetros necesarios para describir una red, haciéndolos más eficientes. Las redes ideales son un concepto nuevo, pero durante mucho tiempo se han utilizado clases de redes similares. Por ejemplo, las redes cíclicas, un caso especial de redes ideales, se utilizan en NTRUEncrypt y NTRUSign .
Las redes ideales también forman la base para la criptografía resistente a ataques informáticos cuánticos basada en el Ring Learning with Errors. [2] Estos criptosistemas son demostrablemente seguros bajo el supuesto de que el problema del vector más corto (SVP) es difícil en estas redes ideales.
En términos generales, las redes ideales son redes correspondientes a ideales en anillos de la forma para algún polinomio de grado irreducible . [1] Todas las definiciones de redes ideales de trabajos anteriores son ejemplos de la siguiente noción general: sea un anillo cuyo grupo aditivo es isomorfo a (es decir, es un módulo libre de rango ), y sea un isomorfismo aditivo mapeo a alguna red en un espacio vectorial real de dimensiones (por ejemplo, ). La familia de celosías ideales para el anillo bajo el incrustamiento es el conjunto de todas las celosías , donde es un ideal en [3]
Sea un polinomio mónico de grado y considere el anillo del cociente .
Utilizando el conjunto estándar de representantes y la identificación de polinomios con vectores, el anillo cociente es isomorfo (como grupo aditivo ) a la red de enteros , y cualquier ideal define una subred de enteros correspondiente .
Una red ideal es una red de números enteros tal que para algún polinomio mónico de grado e ideal .
Resulta que las propiedades relevantes para que la función resultante sea resistente a colisiones son:
La primera propiedad implica que cada ideal del anillo define una red de rango completo y juega un papel fundamental en las pruebas.
Lema: Todo ideal de , donde es un polinomio entero irreducible y mónico de grado , es isomorfo a una red de rango completo en .
Ding y Lindner [4] demostraron que es posible distinguir las redes ideales de las generales en tiempo polinómico y demostraron que, en la práctica, las redes elegidas al azar nunca son ideales. Sólo consideraron el caso en el que la red tiene rango completo, es decir, la base está formada por vectores lineales independientes . Esta no es una restricción fundamental porque Lyubashevsky y Micciancio han demostrado que si una red es ideal con respecto a un polinomio mónico irreducible, entonces tiene rango completo, como se indica en el lema anterior.
Algoritmo: identificación de redes ideales con bases de rango completo
Datos: una base de rango completo Resultado: verdadero y , si abarca una red ideal con respecto a , en caso contrario, falso .
donde la matriz M es
Usando este algoritmo, se puede ver que muchas redes no son redes ideales . Por ejemplo, sea y , entonces
es ideal, pero
no es. con un ejemplo dado por Lyubashevsky y Micciancio. [5]
Al realizar el algoritmo y referirse a la base como B, la matriz B ya está en la forma normal de Hermite, por lo que no es necesario el primer paso. El determinante es la matriz conjugada .
y finalmente el producto es
En este punto, el algoritmo se detiene, porque todas menos la última columna de tienen que ser cero si abarcaran una red ideal .
Micciancio [6] introdujo la clase de redes cíclicas estructuradas, que corresponden a ideales en anillos polinomiales , y presentó la primera función unidireccional demostrablemente segura basada en la dureza del peor de los casos de la restricción de Poly( n )-SVP a redes cíclicas. . (El problema γ -SVP consiste en calcular un vector distinto de cero de una red dada, cuya norma no es más de γ veces mayor que la norma de un vector de red distinto de cero más corto.) Al mismo tiempo, gracias a su carácter algebraico estructura, esta función unidireccional disfruta de una alta eficiencia comparable al tiempo de evaluación del esquema NTRU y al costo de almacenamiento). Posteriormente, Lyubashevsky y Micciancio [5] e independientemente Peikert y Rosen [7] mostraron cómo modificar la función de Micciancio para construir una función hash eficiente y demostrablemente segura resistente a colisiones . Para ello, introdujeron la clase más general de redes ideales , que corresponden a ideales en anillos polinomiales . La resistencia a la colisión depende de la dureza de la restricción de Poly(n)-SVP a redes ideales (llamadas Poly( n )-Ideal-SVP). El problema de búsqueda de colisiones en el caso promedio es un problema computacional natural llamado Ideal-SIS, que ha demostrado ser tan difícil como los peores casos de Ideal-SVP. También se han propuesto esquemas de firma eficientes y demostrablemente seguros a partir de redes ideales , [1] [8] pero construir un cifrado de clave pública eficiente y demostrablemente seguro a partir de redes ideales era un problema abierto interesante .
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 y proporcionó una descripción de vanguardia de un intercambio de claves resistente a cuánticos utilizando Ring LWE . El artículo [9] apareció en 2012 después de que se presentara una solicitud de patente provisional en 2012. En 2014, Peikert [10] presentó un esquema de transporte clave siguiendo la misma idea básica de Ding, donde la nueva idea de enviar señales adicionales para redondear en Ding También se utiliza la construcción. Varios años antes, Vadim Lyubashevsky realizó una firma digital utilizando los mismos conceptos en "Lattice Signatures Without Trapdoors". [11] Juntos, el trabajo de Peikert y Lyubashevsky proporciona un conjunto de algoritmos resistentes a ataques cuánticos basados en Ring-LWE con las mismas reducciones de seguridad.
La principal utilidad de las redes ideales en criptografía surge del hecho de que se pueden construir funciones hash muy eficientes y prácticas resistentes a colisiones basadas en la dificultad de encontrar un vector aproximado más corto en dichas redes. [1] Funciones hash resistentes a colisiones construidas independientemente por Peikert y Rosen, [7] así como por Lyubashevsky y Micciancio, basadas en redes ideales (una generalización de redes cíclicas), y proporcionaron una implementación rápida y práctica. [3] Estos resultados allanaron el camino para otras construcciones criptográficas eficientes, incluidos esquemas de identificación y firmas.
Lyubashevsky y Micciancio [5] dieron construcciones de funciones hash eficientes resistentes a colisiones que pueden demostrarse seguras basándose en la dureza del peor de los casos del problema del vector más corto para redes ideales . Definieron familias de funciones hash como: Dado un anillo , donde es un polinomio de grado monónico e irreducible y es un número entero de orden aproximado , genera elementos aleatorios , donde es una constante. La tupla ordenada determina la función hash. Mapeará elementos en , donde hay un subconjunto estratégicamente elegido de , a . Para un elemento , el hash es . Aquí el tamaño de la clave (la función hash ) es , y la operación se puede realizar a tiempo utilizando la Transformada Rápida de Fourier (FFT) [ cita requerida ] , para la elección adecuada del polinomio . Dado que es una constante, el hash requiere tiempo . Demostraron que la familia de funciones hash es resistente a las colisiones al mostrar que si hay un algoritmo de tiempo polinomial que logra con una probabilidad no despreciable encontrar tal que , para una función hash elegida al azar , entonces surge un determinado problema llamado el " problema del vector más corto ". ”se puede resolver en tiempo polinomial para cada ideal del anillo .
Basado en el trabajo de Lyubashevsky y Micciancio en 2006, Micciancio y Regev [12] definieron el siguiente algoritmo de funciones hash basadas en redes ideales :
Aquí hay parámetros, f es un vector y es una matriz de bloques con bloques estructurados .
Encontrar vectores cortos en promedio (incluso con probabilidad polinómica inversa) es tan difícil como resolver varios problemas de red (como SVP y SIVP aproximados) en el peor de los casos sobre redes ideales , siempre que el vector f satisfaga las dos propiedades siguientes:
La primera propiedad la satisface el vector correspondiente a las matrices circulantes , porque todas las coordenadas de [F∗u]v están acotadas por 1, y por tanto . Sin embargo, el polinomio correspondiente a no es irreducible porque influye en , y es por eso que las colisiones se pueden encontrar de manera eficiente. Por lo tanto, no es una buena opción obtener funciones hash resistentes a colisiones , pero son posibles muchas otras opciones. Por ejemplo, algunas opciones de f para las cuales se satisfacen ambas propiedades (y por lo tanto, dan como resultado funciones hash resistentes a colisiones con garantías de seguridad en el peor de los casos) son
Los esquemas de firmas digitales se encuentran entre las primitivas criptográficas más importantes. Se pueden obtener utilizando funciones unidireccionales basadas en la dureza del peor de los casos de problemas de red. Sin embargo, no son prácticos. Desde que se aplicó el problema del aprendizaje con errores en un contexto criptográfico, se han desarrollado una serie de nuevos esquemas de firma digital basados en el aprendizaje con errores, el aprendizaje en anillo con errores y las redes de trampilla.
Su construcción directa de firmas digitales se basa en la complejidad de aproximar el vector más corto en redes ideales (por ejemplo, cíclicas). [8] El esquema de Lyubashevsky y Micciancio [8] tiene garantías de seguridad en el peor de los casos basadas en redes ideales y es la construcción más asintóticamente eficiente conocida hasta la fecha, lo que produce algoritmos de generación y verificación de firmas que se ejecutan en un tiempo casi lineal . [12]
Uno de los principales problemas abiertos que surgió de su trabajo es la construcción de una firma única con eficiencia similar, pero basada en un supuesto de dureza más débil . Por ejemplo, sería fantástico proporcionar una firma única con seguridad basada en la dureza de aproximar el problema del vector más corto (SVP) (en redes ideales ) dentro de un factor de . [8]
Su construcción se basa en una transformación estándar de firmas de un solo uso (es decir, firmas que permiten firmar de forma segura un único mensaje) a esquemas de firma generales, junto con una construcción novedosa de una firma de un solo uso basada en celosía cuya seguridad se basa en última instancia en la Dureza en el peor de los casos de aproximar el vector más corto en todas las redes correspondientes a los ideales en el anillo para cualquier polinomio irreducible .
Algoritmo de generación de claves: Entrada : polinomio irreducible de grado .
Algoritmo de firma:
Entrada: Mensaje tal que ; clave de firma
Producción:
Algoritmo de verificación:
Entrada: Mensaje ; firma ; clave de verificación
Salida: “ACEPTAR”, si y
“RECHAZAR”, en caso contrario.
La función hash es bastante eficiente y se puede calcular asintóticamente en el tiempo utilizando la Transformada Rápida de Fourier (FFT) sobre números complejos . Sin embargo, en la práctica, esto conlleva unos gastos generales sustanciales. La familia SWIFFT de funciones hash definida por Micciancio y Regev [12] es esencialmente una variante altamente optimizada de la función hash anterior que utiliza (FFT) en . El vector f se establece como igual a una potencia de 2, de modo que el polinomio correspondiente es irreducible . Sea un número primo tal que divida y sea una matriz invertible que se elegirá más adelante . La función hash SWIFFT asigna una clave que consta de vectores elegidos uniformemente y una entrada a donde es como antes y . La multiplicación por la matriz invertible asigna un elegido uniformemente a un elegido uniformemente . Además, si y sólo si . Juntos, estos dos hechos establecen que encontrar colisiones en SWIFFT es equivalente a encontrar colisiones en la función de red ideal subyacente , y la propiedad de resistencia a colisiones de SWIFFT está respaldada por la conexión con los peores problemas de red en redes ideales .
El algoritmo de la función hash SWIFFT es:
Se ha demostrado que el problema de aprendizaje con errores (LWE) es tan difícil como los problemas de red en el peor de los casos y ha servido como base para muchas aplicaciones criptográficas. Sin embargo, estas aplicaciones son ineficientes debido a una sobrecarga cuadrática inherente al uso de LWE . Para obtener aplicaciones LWE verdaderamente eficientes, Lyubashevsky, Peikert y Regev [3] definieron una versión apropiada del problema LWE en una amplia clase de anillos y demostraron su dureza bajo los peores supuestos en redes ideales en estos anillos. Llamaron a su versión LWE ring-LWE.
Sea , donde el parámetro de seguridad es una potencia de 2, lo que lo hace irreducible sobre los racionales. (Este particular proviene de la familia de los polinomios ciclotómicos , los cuales juegan un papel especial en este trabajo).
Sea el anillo de polinomios enteros módulo . Los elementos de (es decir, módulo de residuos ) normalmente se representan mediante polinomios enteros de grado menor que . Sea un módulo primo público suficientemente grande (limitado por un polinomio en ), y sea el anillo de polinomios enteros módulo tanto como . Los elementos de pueden representarse mediante polinomios de grado menor que -cuyos coeficientes son de .
En el anillo descrito anteriormente, el problema R-LWE se puede describir de la siguiente manera. Sea un elemento de anillo uniformemente aleatorio, que se mantiene en secreto. De manera análoga al LWE estándar, el objetivo del atacante es distinguir arbitrariamente muchas 'ecuaciones de anillo ruidosas aleatorias' (independientes) de las verdaderamente uniformes. Más específicamente, las ecuaciones ruidosas tienen la forma , donde a es uniformemente aleatorio y el producto se ve perturbado por algún término de error aleatorio "pequeño", elegido de una determinada distribución sobre .
Dieron una reducción cuántica de SVP aproximado (en el peor de los casos) en redes ideales a la versión de búsqueda de ring-LWE, donde el objetivo es recuperar el secreto (con alta probabilidad, para cualquiera ) de muchos productos ruidosos. Este resultado sigue el esquema general de la reducción cuántica iterativa de Regev para redes generales, [13] pero las redes ideales introducen varios obstáculos técnicos nuevos tanto en los componentes "algebraicos" como en los "geométricos" de la reducción. Ellos [3] utilizaron la teoría algebraica de números, en particular, la incorporación canónica de un campo numérico y el teorema del resto chino para superar estos obstáculos. Obtuvieron el siguiente teorema:
Teorema Sea un campo numérico arbitrario de grado . Sea arbitrario y sea el módulo entero (racional) tal que . Hay una reducción cuántica probabilística en tiempo polinomial de - a - , donde .
En 2013, Guneysu, Lyubashevsky y Poppleman propusieron un esquema de firma digital basado en el problema Ring Learning with Errors. [14] En 2014, Peikert presentó un intercambio de claves de aprendizaje en anillo con errores (RLWE-KEX) en su artículo, "Lattice Cryptography for the Internet". [10] Esto fue desarrollado aún más por el trabajo de Singh. [15]
Stehle, Steinfeld, Tanaka y Xagawa [16] definieron una variante estructurada del problema LWE (Ideal-LWE) para describir un esquema de cifrado de clave pública eficiente basado en la dureza del peor de los casos del SVP aproximado en redes ideales. Este es el primer esquema de cifrado de clave pública seguro por CPA cuya seguridad se basa en la dureza de los peores casos de -Ideal-SVP contra ataques cuánticos subexponenciales. Logra una eficiencia asintóticamente óptima: la longitud de la clave pública/privada es bits y el costo amortizado de cifrado/descifrado son operaciones de bits por bit de mensaje (cifrar bits a la vez, con un costo). El supuesto de seguridad aquí es que -Ideal-SVP no puede resolverse mediante ningún algoritmo cuántico de tiempo subexponencial. Cabe señalar que esto es más sólido que los supuestos de seguridad de la criptografía de clave pública estándar . Por otro lado, a diferencia de la mayor parte de la criptografía de clave pública , la criptografía basada en celosía permite seguridad contra ataques cuánticos subexponenciales.
La mayoría de los criptosistemas basados en redes generales se basan en la dureza promedio del aprendizaje con errores (LWE) . Su esquema se basa en una variante estructurada de LWE, a la que llaman Ideal-LWE. Necesitaban introducir algunas técnicas para sortear dos dificultades principales que surgen de la restricción a redes ideales. En primer lugar, todos los criptosistemas anteriores basados en redes no estructuradas hacen uso de la reducción clásica de Regev del peor de los casos al caso promedio del problema de decodificación de distancia limitada (BDD) a LWE (este es el paso clásico en la reducción cuántica de SVP a LWE ). Esta reducción explota la falta de estructura de las redes consideradas y no parece trasladarse a las redes estructuradas involucradas en Ideal-LWE. En particular, la independencia probabilística de las filas de las matrices LWE permite considerar una sola fila. En segundo lugar, el otro ingrediente utilizado en criptosistemas anteriores, a saber, la reducción de Regev de la variante computacional de LWE a su variante decisional, también parece fallar para Ideal-LWE: se basa en la independencia probabilística de las columnas de las matrices LWE .
Para superar estas dificultades, evitaron el paso clásico de la reducción. En cambio, utilizaron el paso cuántico para construir una nueva reducción cuántica de casos promedio desde SIS (problema de búsqueda de colisiones de casos promedio) a LWE . También funciona desde Ideal-SIS hasta Ideal-LWE. Combinado con la reducción del Ideal-SVP en el peor de los casos al Ideal-SIS promedio, obtuvieron una reducción cuántica de Ideal-SVP a Ideal-LWE. Esto muestra la dureza de la variante computacional de Ideal-LWE. Como no obtuvieron la dureza de la variante decisional, utilizaron una función genérica incondicional para derivar bits pseudoaleatorios para el cifrado. Por eso necesitaban asumir la dureza exponencial de SVP .
Un esquema de cifrado totalmente homomórfico (FHE) es aquel que permite el cálculo de datos cifrados, sin necesidad de descifrarlos primero. El problema de construir un esquema de cifrado totalmente homomórfico fue planteado por primera vez por Rivest, Adleman y Dertouzos [17] en 1978, poco después de la invención de RSA por Rivest, Adleman y Shamir. [18]
Un esquema de cifrado es homomórfico para circuitos en si, para cualquier circuito ,
dado , , y ,
sostiene eso .
es completamente homomórfico si es homomórfico para todos los circuitos de tamaño donde está el parámetro de seguridad del esquema.
En 2009, Gentry [19] propuso la primera solución al problema de construir un esquema de cifrado totalmente homomórfico . Su esquema se basó en redes ideales.