Criptografía basada en retículos

La criptografía basada en retículos es el término genérico para las construcciones de primitivas criptográficas que involucran retículos , ya sea en la construcción misma o en la prueba de seguridad. Las construcciones basadas en retículos respaldan estándares importantes de criptografía postcuántica . ^{[ 1 ]} A diferencia de los esquemas de clave pública más utilizados y conocidos, como RSA , Diffie-Hellman o los criptosistemas de curva elíptica —que, teóricamente, podrían ser vulnerados utilizando el algoritmo de Shor en una computadora cuántica— , algunas construcciones basadas en retículos parecen ser resistentes a los ataques tanto de computadoras clásicas como cuánticas. Además, muchas construcciones basadas en retículos se consideran seguras bajo el supuesto de que ciertos problemas computacionales de retículos bien estudiados no pueden resolverse de manera eficiente.

En 2024, el NIST anunció el Estándar de Firma Digital Basado en Módulos y Retículos para la criptografía postcuántica. ^{[ 2 ]}

En 1996, Miklós Ajtai introdujo la primera construcción criptográfica basada en retículos cuya seguridad podía fundamentarse en la dificultad de problemas de retículos bien estudiados, ^{[ 3 ]} y Cynthia Dwork demostró que un cierto problema de retículos de caso promedio, conocido como soluciones enteras cortas (SIS), es al menos tan difícil de resolver como un problema de retículos de peor caso . ^{[ 4 ]} Luego, mostró una función hash criptográfica cuya seguridad es equivalente a la dificultad computacional de SIS.

En 1998, Jeffrey Hoffstein , Jill Pipher y Joseph H. Silverman introdujeron un esquema de cifrado de clave pública basado en retículos , conocido como NTRU . ^{[ 5 ]} Sin embargo, no se sabe que su esquema sea al menos tan difícil como resolver un problema de retículos en el peor de los casos.

El primer esquema de cifrado de clave pública basado en retículos cuya seguridad se demostró bajo supuestos de dificultad en el peor de los casos fue introducido por Oded Regev en 2005, ^{[ 6 ]} junto con el problema de aprendizaje con errores (LWE). Desde entonces, gran parte del trabajo posterior se ha centrado en mejorar la prueba de seguridad de Regev ^{[ 7 ] [ 8 ]} y en mejorar la eficiencia del esquema original. ^{[ 9 ] [ 10 ] [ 11 ] [ 12 ]} Se ha dedicado mucho más trabajo a la construcción de primitivas criptográficas adicionales basadas en LWE y problemas relacionados. Por ejemplo, en 2009, Craig Gentry introdujo el primer esquema de cifrado totalmente homomórfico , que se basó en un problema de retículos. ^{[ 13 ]}

En álgebra lineal , una red${\displaystyle L\subset \mathbb {R} ^{n}}$es el conjunto de todas las combinaciones lineales enteras de vectores de una base${\displaystyle \{\mathbf {b} _{1},\ldots ,\mathbf {b} _{n}\}}$de${\displaystyle \mathbb {R} ^{n}}$. En otras palabras, ${\displaystyle L={\Big \{}\sum a_{i}\mathbf {b} _{i}:a_{i}\in \mathbb {Z} {\Big \}}.}$ Por ejemplo,${\displaystyle \mathbb {Z} ^{n}}$es una red, generada por la base estándar para${\displaystyle \mathbb {R} ^{n}}$Fundamentalmente, la base de una red no es única. Por ejemplo, los vectores${\displaystyle (3,1,4)}$,${\displaystyle (1,5,9)}$, y${\displaystyle (2,-1,0)}$formar una base alternativa para${\displaystyle \mathbb {Z} ^{3}}$.

El problema computacional basado en retículos más importante es el problema del vector más corto (SVP o a veces GapSVP), que pide una longitud euclidiana mínima aproximada de un vector de retículo no nulo. Se cree que este problema es difícil de resolver de manera eficiente, incluso con factores de aproximación que son polinomiales en${\displaystyle n}$, e incluso con una computadora cuántica. Se sabe que muchas (aunque no todas) las construcciones criptográficas basadas en retículos son seguras si SVP es realmente difícil en este régimen.

Esta sección presenta una selección de esquemas basados ​​en retículos, agrupados por primitiva.

Las construcciones criptográficas basadas en retículos son muy prometedoras para la criptografía postcuántica de clave pública . ^{[ 38 ]} De hecho, las principales formas alternativas de criptografía de clave pública son esquemas basados ​​en la dificultad de la factorización y problemas relacionados , y esquemas basados ​​en la dificultad del logaritmo discreto y problemas relacionados . Sin embargo, se sabe que tanto la factorización como el problema del logaritmo discreto se pueden resolver en tiempo polinomial en una computadora cuántica . ^{[ 39 ]} Además, los algoritmos para la factorización tienden a generar algoritmos para el logaritmo discreto, y viceversa. Esto motiva aún más el estudio de construcciones basadas en supuestos alternativos, como la dificultad de los problemas de retículos.

Se sabe que muchos esquemas criptográficos basados ​​en retículos son seguros asumiendo la dificultad en el peor de los casos de ciertos problemas de retículos. ^{[ 3 ] [ 6 ] [ 7 ]} Es decir, si existe un algoritmo que puede romper eficientemente el esquema criptográfico con una probabilidad no despreciable, entonces existe un algoritmo eficiente que resuelve un cierto problema de retículos para cualquier entrada. Sin embargo, para las construcciones prácticas basadas en retículos (como los esquemas basados ​​en NTRU e incluso los esquemas basados ​​en LWE con parámetros eficientes), no se conocen garantías de seguridad significativas basadas en reducciones.

Las evaluaciones de los niveles de seguridad proporcionados por argumentos de reducción de problemas difíciles —basadas en tamaños de parámetros recomendados, estimaciones estándar de la complejidad computacional de los problemas difíciles y un examen detallado de los pasos en las reducciones— se denominan seguridad concreta y, a veces, seguridad demostrable orientada a la práctica . ^{[ 40 ]} Algunos autores que han investigado la seguridad concreta para criptosistemas basados ​​en retículos han encontrado que los resultados de seguridad demostrable para tales sistemas no proporcionan ninguna seguridad concreta significativa para valores prácticos de los parámetros. ^{[ 41 ]}

Para muchas primitivas criptográficas, las únicas construcciones conocidas se basan en retículos u objetos estrechamente relacionados. Estas primitivas incluyen el cifrado totalmente homomórfico , ^{[ 13 ]} la ofuscación de indistinguibilidad , ^{[ 42 ]} los mapas multilineales criptográficos y el cifrado funcional . ^{[ 42 ]}

• Problemas de retículos
• Aprender de los errores
• Cifrado homomórfico
• Criptografía postcuántica
• Aprendizaje en anillo con errores
• Aprendizaje en anillo con intercambio de claves de errores

• Goldreich, Oded; Goldwasser, Shafi; Halevi, Shai (1997). «Sistemas criptográficos de clave pública a partir de problemas de reducción reticular». Crypto '97: Actas de la 17.ª Conferencia Internacional Anual de Criptología sobre Avances en Criptología . Londres, Reino Unido: Springer-Verlag. pp. 112–131 . doi : 10.1007/BFb0052231 . ISBN  978-3-540-63384-6.
• Regev, Oded (2006). «Criptografía basada en retículos». Avances en criptología (CRYPTO) . Springer-Verlag. pp. 131–141 . doi : 10.1007/11818175_8 . ISBN  978-3-540-37432-9.

• Demostración de Dilithium en Excel : Ejemplo de implementación y demostración en Excel (sin macros) por Tim Wambach.