celosía ideal

Objeto matemático

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.

Introducción

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] ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle R}$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle n}$ ${\displaystyle \sigma }$ ${\displaystyle R}$ ${\displaystyle \sigma (R)}$ ${\displaystyle n}$ ${\displaystyle \mathbb {R} ^{n}}$ ${\displaystyle R}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma (I)}$ ${\displaystyle I}$ ${\displaystyle R.}$

Definición

Notación

Sea un polinomio mónico de grado y considere el anillo del cociente . ${\displaystyle f\in \mathbb {Z} [x]}$ ${\displaystyle n}$ ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$

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 . ${\displaystyle \lbrace (g{\bmod {f}}):g\in \mathbb {Z} [x]\rbrace }$ ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle I\subseteq \mathbb {Z} [x]/\langle f\rangle }$ ${\displaystyle {\mathcal {L}}(I)\subseteq \mathbb {Z} ^{n}}$

Una red ideal es una red de números enteros tal que para algún polinomio mónico de grado e ideal . ${\displaystyle {\mathcal {L}}(B)\subseteq \mathbb {Z} ^{n}}$ ${\displaystyle B=\lbrace g{\bmod {f}}:g\in I\rbrace }$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle I\subseteq \mathbb {Z} [x]/\langle f\rangle }$

Propiedades relacionadas

Resulta que las propiedades relevantes para que la función resultante sea resistente a colisiones son: ${\displaystyle f}$

• ${\displaystyle f}$debería ser irreductible .
• la norma del anillo no es mucho mayor que la de cualquier polinomio , en sentido cuantitativo. ${\displaystyle \lVert g\rVert _{f}}$ ${\displaystyle \lVert g\rVert _{\infty }}$ ${\displaystyle g}$

La primera propiedad implica que cada ideal del anillo define una red de rango completo y juega un papel fundamental en las pruebas. ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$ ${\displaystyle \mathbb {Z} ^{n}}$

Lema: Todo ideal de , donde es un polinomio entero irreducible y mónico de grado , es isomorfo a una red de rango completo en . ${\displaystyle I}$ ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$ ${\displaystyle f}$ ${\displaystyle n}$ ${\displaystyle \mathbb {Z} ^{n}}$

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. ${\displaystyle n}$

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 . ${\displaystyle B\in \mathbb {Z} ^{(n,n)}}$
${\displaystyle {\textbf {q}}}$ ${\displaystyle B}$ ${\displaystyle {\textbf {q}}}$

1. Transformarse en HNF ${\displaystyle B}$
2. Calcular , y ${\displaystyle A={\rm {adj}}(B)}$ ${\displaystyle d=\det(B)}$ ${\displaystyle z=B_{(n,n)}}$
3. Calcular el producto ${\displaystyle P=AMB{\bmod {d}}}$
4. si sólo la última columna de P es distinta de cero , entonces
5. establecido para igualar esta columna ${\displaystyle c=P_{(\centerdot ,n)}}$
6. de lo contrario devolverá falso
7. si para entonces ${\displaystyle z\mid c_{i}}$ ${\displaystyle i=1,\ldots ,n}$
8. use CRT para encontrar y ${\displaystyle q^{\ast }\equiv (c/z){\bmod {(}}d/z)}$ ${\displaystyle q^{\ast }\equiv 0{\bmod {\ }}z}$
9. de lo contrario devolverá falso
10. si entonces ${\displaystyle Bq^{\ast }\equiv 0{\bmod {(}}d/z)}$
11. devolver verdadero , ${\displaystyle q=Bq^{\ast }/d}$
12. de lo contrario devolverá falso

donde la matriz M es

${\displaystyle M={\begin{pmatrix}0&\cdot &\cdot &\cdot &0\\&&&&\cdot \\&&&&\cdot \\I_{n-1}&&&&\cdot \\&&&&0\end{pmatrix}}}$

Usando este algoritmo, se puede ver que muchas redes no son redes ideales . Por ejemplo, sea y , entonces ${\displaystyle n=2}$ ${\displaystyle k\in \mathbb {Z} \smallsetminus \lbrace 0,\pm 1\rbrace }$

${\displaystyle B_{1}={\begin{pmatrix}k&0\\0&1\end{pmatrix}}}$

es ideal, pero

${\displaystyle B_{2}={\begin{pmatrix}1&0\\0&k\end{pmatrix}}}$

no es. con un ejemplo dado por Lyubashevsky y Micciancio. ^[5] ${\displaystyle B_{2}}$ ${\displaystyle k=2}$

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 . ${\displaystyle d=2}$

${\displaystyle A={\begin{pmatrix}2&0\\0&1\end{pmatrix}},}$

${\displaystyle M={\begin{pmatrix}0&0\\1&0\end{pmatrix}}}$

y finalmente el producto es ${\displaystyle P=AMB{\bmod {d}}}$

${\displaystyle P={\begin{pmatrix}0&0\\1&0\end{pmatrix}}.}$

En este punto, el algoritmo se detiene, porque todas menos la última columna de tienen que ser cero si abarcaran una red ideal . ${\displaystyle P}$ ${\displaystyle B}$

Uso en criptografía

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 . ${\displaystyle \mathbb {Z} [x]/(x^{n}-1)}$ ${\displaystyle {\tilde {O}}(n)}$ ${\displaystyle \mathbb {Z} [x]/f(x)}$

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.

Funciones hash eficientes y resistentes a colisiones

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 . ${\displaystyle R=\mathbb {Z} _{p}[x]/\langle f\rangle }$ ${\displaystyle f\in \mathbb {Z} _{p}[x]}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n^{2}}$ ${\displaystyle m}$ ${\displaystyle a_{1},\dots ,a_{m}\in R}$ ${\displaystyle m}$ ${\displaystyle m}$ ${\displaystyle h=(a_{1},\ldots ,a_{m})\in R^{m}}$ ${\displaystyle D^{m}}$ ${\displaystyle D}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle b=(b_{1},\ldots ,b_{m})\in D^{m}}$ ${\displaystyle h(b)=\sum _{i=1}^{m}\alpha _{i}\centerdot b_{i}}$ ${\displaystyle O(mn\log p)=O(n\log n)}$ ${\displaystyle \alpha _{i}\centerdot b_{i}}$ ${\displaystyle O(n\log n\log \log n)}$ ${\displaystyle f}$ ${\displaystyle m}$ ${\displaystyle O(n\log n\log \log n)}$ ${\displaystyle b\neq b'\in D^{m}}$ ${\displaystyle h(b)=h(b')}$ ${\displaystyle h\in R^{m}}$ ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$

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 :

• Parámetros: Enteros con y vector f . ${\displaystyle q,n,m,d}$ ${\displaystyle n\mid m}$ ${\displaystyle \in \mathbb {Z} ^{n}}$
• Clave: vectores elegidos de forma independiente y uniforme al azar en . ${\displaystyle m/n}$ ${\displaystyle a_{1},\ldots ,a_{m/n}}$ ${\displaystyle \mathbb {Z} _{q}^{n}}$
• Función hash: dada por . ${\displaystyle f_{A}:\lbrace 0,\ldots ,d-1\rbrace ^{m}\longrightarrow \mathbb {Z} _{q}^{n}}$ ${\displaystyle f_{A}(y)=[F\ast a_{1}|\ldots |F\ast a_{m/n}]y{\bmod {\ }}q}$

Aquí hay parámetros, f es un vector y es una matriz de bloques con bloques estructurados . ${\displaystyle n,m,q,d}$ ${\displaystyle \mathbb {Z} ^{n}}$ ${\displaystyle A}$ ${\displaystyle A^{(i)}=F\ast a^{(i)}}$

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: ${\displaystyle \Lambda _{q}^{\perp }([F\ast a_{1}|\ldots |F\ast a_{m/n}])}$

• Para dos vectores unitarios cualesquiera u , v , el vector [F∗u]v tiene una norma pequeña (digamos, polinomio en) , típicamente . ${\displaystyle n}$ ${\displaystyle O({\sqrt {n}}))}$
• El polinomio es irreducible sobre los números enteros, es decir, no se factoriza en el producto de polinomios enteros de menor grado. ${\displaystyle f(x)=x^{n}+f_{n}x^{n-1}+\cdots +f_{1}\in \mathbb {Z} [x]}$

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 ${\displaystyle \mathbf {F} =(-1,0,\ldots ,0)}$ ${\displaystyle \lVert [{\textbf {F}}\ast {\textbf {u}}]{\textbf {v}}\rVert \leq {\sqrt {n}}}$ ${\displaystyle x^{n}-1}$ ${\displaystyle \mathbf {f} =(-1,0,\ldots ,0)}$ ${\displaystyle (x-1)(x^{n-1}+x^{n-2}+\cdots +x+1)}$ ${\displaystyle \mathbf {f} =(-1,0,\ldots ,0)}$

• ${\displaystyle \mathbf {f} =(1,\ldots ,1)\in \mathbb {Z} ^{n}}$donde es primo, y ${\displaystyle n+1}$
• ${\displaystyle \mathbf {f} =(1,0,\ldots ,0)\in \mathbb {Z} ^{n}}$para igual a una potencia de 2. ${\displaystyle n}$

Firmas digitales

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] ${\displaystyle {\tilde {O}}(n)}$

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 . ${\displaystyle \mathbb {Z} [x]/\langle f\rangle }$ ${\displaystyle f}$

Algoritmo de generación de claves: Entrada : polinomio irreducible de grado . ${\displaystyle 1^{n}}$ ${\displaystyle f\in \mathbb {Z} }$ ${\displaystyle n}$

1. Colocar , , ${\displaystyle p\longleftarrow (\varphi n)^{3}}$ ${\displaystyle m\longleftarrow \lceil \log n\rceil }$ ${\displaystyle R\longleftarrow \mathbb {Z} _{p}[x]/\langle f\rangle }$
2. Para todo positivo , dejemos que los conjuntos y se definan como: ${\displaystyle i}$ ${\displaystyle DK_{i}}$ ${\displaystyle DL_{i}}$

${\displaystyle DK_{i}=\lbrace {\hat {y}}\in R^{m}}$tal que ${\displaystyle \lVert {\hat {y}}\rVert _{\infty }\leq 5ip^{1/m}\rbrace }$

${\displaystyle DL_{i}=\lbrace {\hat {y}}\in R^{m}}$tal que ${\displaystyle \lVert {\hat {y}}\rVert _{\infty }\leq 5in\varphi p^{1/m}\rbrace }$

1. Elija uniformemente aleatorio ${\displaystyle h\in {\mathcal {H}}_{R,m}}$
2. Elija una cadena uniformemente aleatoria ${\displaystyle r\in \lbrace 0,1\rbrace ^{\lfloor \log ^{2}n\rfloor }}$
3. si entonces ${\displaystyle r=0^{\lfloor \log ^{2}n\rfloor }}$
4. Colocar ${\displaystyle j=\lfloor \log ^{2}n\rfloor }$
5. demás
6. Establecer en la posición del primer 1 en la cadena. ${\displaystyle j}$ ${\displaystyle r}$
7. terminara si
8. Elija de forma independiente y uniforme al azar de y respectivamente ${\displaystyle {\hat {k}},{\hat {l}}}$ ${\displaystyle DK_{j}}$ ${\displaystyle DL_{j}}$
9. Clave de firma: . Clave de verificación: ${\displaystyle ({\hat {k}},{\hat {l}})}$ ${\displaystyle (h,h({\hat {k}}),h({\hat {l}}))}$

Algoritmo de firma:

Entrada: Mensaje tal que ; clave de firma ${\displaystyle z\in R}$ ${\displaystyle \lVert z\rVert _{\infty }\leq 1}$ ${\displaystyle ({\hat {k}},{\hat {l}})}$

Producción: ${\displaystyle {\hat {s}}\longleftarrow {\hat {k}}z+{\hat {l}}}$

Algoritmo de verificación:

Entrada: Mensaje ; firma ; clave de verificación ${\displaystyle z}$ ${\displaystyle {\hat {s}}}$ ${\displaystyle (h,h({\hat {k}}),h({\hat {l}}))}$

Salida: “ACEPTAR”, si y ${\displaystyle \lVert {\hat {s}}\rVert _{\infty }\leq 10\varphi p^{1/m}n\log ^{2}n}$ ${\displaystyle {\hat {s}}={\hat {k}}z+{\hat {l}}}$

“RECHAZAR”, en caso contrario.

La función hash SWIFFT

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 . ${\displaystyle {\tilde {O}}(m)}$ ${\displaystyle \mathbb {Z} _{q}}$ ${\displaystyle (1,0,\dots ,0)\in \mathbb {Z} ^{n}}$ ${\displaystyle n}$ ${\displaystyle x^{n}+1}$ ${\displaystyle q}$ ${\displaystyle 2n}$ ${\displaystyle q-1}$ ${\displaystyle {\textbf {W}}\in \mathbb {Z} _{q}^{n\times n}}$ ${\displaystyle \mathbb {Z} _{q}}$ ${\displaystyle {\tilde {a}}^{(1)},\ldots ,{\tilde {a}}^{(m/n)}}$ ${\displaystyle m/n}$ ${\displaystyle \mathbb {Z} _{q}^{n}}$ ${\displaystyle y\in \lbrace 0,\ldots ,d-1\rbrace ^{m}}$ ${\displaystyle {\textbf {W}}^{\centerdot }f_{A}(y){\bmod {\ }}q}$ ${\displaystyle {\textbf {A}}=[{\textbf {F}}\ast \alpha ^{(1)},\ldots ,{\textbf {F}}\ast \alpha ^{(m/n)}]}$ ${\displaystyle \alpha ^{(i)}={\textbf {W}}^{-1}{\tilde {a}}^{(i)}{\bmod {q}}}$ ${\displaystyle {\textbf {W}}^{-1}}$ ${\displaystyle {\tilde {a}}\in \mathbb {Z} _{q}^{n}}$ ${\displaystyle \alpha \in \mathbb {Z} _{q}^{n}}$ ${\displaystyle {\textbf {W}}^{\centerdot }f_{A}(y)={\textbf {W}}^{\centerdot }f_{A}(y'){\pmod {q}}}$ ${\displaystyle f_{A}(y)=f_{A}(y'){\pmod {q}}}$ ${\displaystyle f_{A}}$

El algoritmo de la función hash SWIFFT es:

• Parámetros: números enteros que son una potencia de 2, son primos y . ${\displaystyle n,m,q,d}$ ${\displaystyle n}$ ${\displaystyle q}$ ${\displaystyle 2n\mid (q-1)}$ ${\displaystyle n\mid m}$
• Clave: vectores elegidos de forma independiente y uniforme al azar en . ${\displaystyle m/n}$ ${\displaystyle {\tilde {a}}_{1},\ldots ,{\tilde {a}}_{m/n}}$ ${\displaystyle \mathbb {Z} _{q}^{n}}$
• Entrada: vectores . ${\displaystyle m/n}$ ${\displaystyle y^{(1)},\dots ,y^{(m/n)}\in \lbrace 0,\dots ,d-1\rbrace ^{n}}$
• Salida: el vector , donde está el producto vectorial por componentes. ${\displaystyle \sum _{i=1}^{m/n}{\tilde {a}}^{(i)}\odot ({\textbf {W}}y^{(i)})\in \mathbb {Z} _{q}^{n}}$ ${\displaystyle \odot }$

Aprender con errores (LWE)

Anillo-LWE

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). ${\displaystyle f(x)=x^{n}+1\in \mathbb {Z} [x]}$ ${\displaystyle n}$ ${\displaystyle f(x)}$ ${\displaystyle f(x)}$

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 . ${\displaystyle R=\mathbb {Z} [x]/\langle f(x)\rangle }$ ${\displaystyle f(x)}$ ${\displaystyle R}$ ${\displaystyle f(x)}$ ${\displaystyle n}$ ${\displaystyle q\equiv 1{\bmod {2}}n}$ ${\displaystyle n}$ ${\displaystyle R_{q}=R/\langle q\rangle =\mathbb {Z} _{q}[x]/\langle f(x)\rangle }$ ${\displaystyle f(x)}$ ${\displaystyle q}$ ${\displaystyle R_{q}}$ ${\displaystyle n}$ ${\displaystyle \lbrace 0,\dots ,q-1\rbrace }$

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 . ${\displaystyle s=s(x)\in R_{q}}$ ${\displaystyle (a,b\approx a\centerdot s)\in R_{q}\times R_{q}}$ ${\displaystyle a\centerdot s}$ ${\displaystyle R}$

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: ${\displaystyle R}$ ${\displaystyle s\in R_{q}}$ ${\displaystyle s}$

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 . ${\displaystyle K}$ ${\displaystyle n}$ ${\displaystyle \alpha =\alpha (n)\in (0,1)}$ ${\displaystyle q=q(n)\geq 2}$ ${\displaystyle \alpha \centerdot q\geq \omega ({\sqrt {\log n}})}$ ${\displaystyle K}$ ${\displaystyle DGS_{\gamma }}$ ${\displaystyle {\mathcal {O}}_{K}}$ ${\displaystyle LWE_{q,\Psi \leq \alpha }}$ ${\displaystyle \gamma =\eta _{\epsilon }(I)\centerdot \omega ({\sqrt {\log n}})/\alpha }$

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]

Ideal-LWE

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. ${\displaystyle {\tilde {O}}(n^{2})}$ ${\displaystyle {\tilde {O}}(n)}$ ${\displaystyle {\tilde {O}}(1)}$ ${\displaystyle {\tilde {\Omega }}(n)}$ ${\displaystyle {\tilde {O}}(n)}$ ${\displaystyle {\tilde {O}}(n^{2})}$

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 .

Cifrado totalmente homomórfico

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 , ${\displaystyle \varepsilon =({\mathsf {KeyGen}},{\mathsf {Encrypt}},{\mathsf {Decrypt}},{\mathsf {Eval}})}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle C\in {\mathcal {C}}}$

dado , , y , ${\displaystyle PK,SK\leftarrow {\mathsf {KeyGen}}(1^{\lambda })}$ ${\displaystyle y={\mathsf {Encrypt}}(PK,x)}$ ${\displaystyle y'={\mathsf {Eval}}(PK,C,y)}$

sostiene eso . ${\displaystyle {\mathsf {Decrypt}}(SK,y')=C(x)}$

${\displaystyle \varepsilon }$es completamente homomórfico si es homomórfico para todos los circuitos de tamaño donde está el parámetro de seguridad del esquema. ${\displaystyle \operatorname {poly} (\lambda )}$ ${\displaystyle \lambda }$

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.

Ver también

• Criptografía basada en celosía
• Cifrado homomórfico
• Aprendizaje en anillo con intercambio de claves con errores
• Criptografía poscuántica
• Problema de solución de entero corto

Referencias

1. Lyubashevsky, Vadim (2008). "Esquemas de identificación basados ​​en celosía seguros bajo ataques activos" (PDF) . Criptografía de clave pública - PKC 2008 . Apuntes de conferencias sobre informática. vol. 4939, págs. 162-179. doi :10.1007/978-3-540-78440-1_10. ISBN 978-3-540-78439-5.
2. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "Sobre redes ideales y aprendizaje con errores sobre anillos". En Gilbert, Henri (ed.). Avances en Criptología – EUROCRYPT 2010 . Apuntes de conferencias sobre informática. vol. 6110, págs. 1–23. CiteSeerX 10.1.1.297.6108 . doi :10.1007/978-3-642-13190-5_1. ISBN  978-3-642-13189-9.
3. Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (2010). "Sobre redes ideales y aprendizaje con errores sobre anillos". Avances en Criptología – EUROCRYPT 2010 . Apuntes de conferencias sobre informática. vol. 6110, págs. 1–23. doi :10.1007/978-3-642-13190-5_1. ISBN 978-3-642-13189-9.
4. Jintai Ding y Richard Lindner. Identificación de redes ideales. En Cryptology ePrint Archive, Informe 2007/322 , 2007.
5. Lyubashevsky, Vadim; Micciancio, Daniele (2006). "Las mochilas compactas generalizadas son resistentes a las colisiones" (PDF) . Autómatas, Lenguajes y Programación . Apuntes de conferencias sobre informática. vol. 4052, págs. 144-155. doi :10.1007/11787006_13. ISBN 978-3-540-35907-4.
6. Micciancio, Daniele (2007). "Mochilas compactas generalizadas, celosías cíclicas y funciones unidireccionales eficientes". Complejidad computacional . 16 (4): 365–411. doi : 10.1007/s00037-007-0234-9 .
7. Peikert, Chris; Rosen, Alon (2006). "Hashing eficiente resistente a colisiones a partir de supuestos del peor de los casos en celosías cíclicas" (PDF) . Teoría de la Criptografía . Apuntes de conferencias sobre informática. vol. 3876, págs. 145-166. doi :10.1007/11681878_8. ISBN 978-3-540-32731-8. Archivado desde el original (PDF) el 16 de octubre de 2012.
8. Lyubashevsky, Vadim; Micciancio, Daniele (2008). "Firmas digitales asintóticamente eficientes basadas en celosía" (PDF) . Teoría de la Criptografía . Apuntes de conferencias sobre informática. vol. 4948. págs. 37–54. doi :10.1007/978-3-540-78524-8_3. ISBN 978-3-540-78523-1.
9. Ding, Jintai; Xie, Xiang; Lin, Xiaodong (2012). Un esquema simple de intercambio de claves demostrablemente seguro basado en el problema del aprendizaje con errores (PDF) .
10. Peikert, Chris (1 de octubre de 2014). "Criptografía de celosía para Internet". En Mosca, Michele (ed.). Criptografía poscuántica . Apuntes de conferencias sobre informática. vol. 8772. Publicación internacional Springer. págs. 197-219. CiteSeerX 10.1.1.800.4743 . doi :10.1007/978-3-319-11659-4_12. ISBN  978-3-319-11658-7. S2CID  8123895.
11. Lyubashevsky, Vadim (2012). "Firmas enrejadas sin trampillas" (PDF) . Avances en Criptología – EUROCRYPT 2012 . Apuntes de conferencias sobre informática. vol. 7237, págs. 738–755. doi :10.1007/978-3-642-29011-4_43. ISBN 978-3-642-29010-7.
12. Micciancio, Daniele; Regev, Oded (2009). "Criptografía basada en celosía" (PDF) . Criptografía poscuántica . págs. 147-191. doi :10.1007/978-3-540-88702-7_5. ISBN 978-3-540-88701-0. Archivado desde el original (PDF) el 23 de julio de 2011.
13. Regev, Oded (2009). "Sobre celosías, aprendizaje con errores, códigos lineales aleatorios y criptografía" (PDF) . Revista de la ACM . 56 (6): 1–40. arXiv : 2401.03703 . doi :10.1145/1568318.1568324. Archivado desde el original (PDF) el 6 de diciembre de 2010.
14. Güneysu, Tim; Lyubashevsky, Vadim; Pöppelmann, Thomas (2012). "Criptografía práctica basada en celosía: un esquema de firma para sistemas integrados" (PDF) . Hardware criptográfico y sistemas integrados - CHES 2012 . Apuntes de conferencias sobre informática. vol. 7428, págs. 530–547. doi :10.1007/978-3-642-33027-8_31. ISBN 978-3-642-33026-1. Archivado desde el original (PDF) el 18 de mayo de 2014.
15. Singh, Vikram (2015). "Un intercambio de claves práctico para Internet utilizando criptografía Lattice". Archivo ePrint de criptología .
16. Stehlé, Damián; Steinfeld, Ron; Tanaka, Keisuke; Xagawa, Keita (2009). "Cifrado de clave pública eficiente basado en redes ideales: (resumen ampliado)" (PDF) . Avances en Criptología – ASIACRYPT 2009 . Apuntes de conferencias sobre informática. vol. 5912, págs. 617–635. doi :10.1007/978-3-642-10366-7_36. ISBN 978-3-642-10365-0.
17. Rivest, R.; Adleman, L.; Dertouzos, M. (1978). «Sobre bancos de datos y homomorfismos de privacidad» (PDF) . En Fundamentos de la informática segura . Prensa académica. págs. 169–180.
18. Rivest, RL; Shamir, A.; Adleman, L. (1978). "Un método para la obtención de firmas digitales y criptosistemas de clave pública". Comunicaciones de la ACM . 21 (2): 120-126. doi :10.1145/359340.359342. hdl : 1721.1/148910 .
19. Gentry, Craig (2009). "Cifrado totalmente homomórfico utilizando redes ideales". Actas del cuadragésimo primer simposio anual de ACM sobre teoría de la informática . págs. 169-178. doi :10.1145/1536414.1536440. ISBN 978-1-60558-506-2.