La criptografía basada en celosía es el término genérico para las construcciones de primitivas criptográficas que involucran celosías , ya sea en la construcción en sí o en la prueba de seguridad. Las construcciones basadas en celosía son actualmente candidatos importantes para la criptografía post-cuántica . A diferencia de los esquemas de clave pública más ampliamente utilizados y conocidos, como los criptosistemas RSA , Diffie-Hellman o de curva elíptica , que, en teoría, podrían ser fácilmente atacados por una computadora cuántica., algunas construcciones basadas en celosías parecen ser resistentes al ataque de computadoras tanto clásicas como cuánticas. Además, muchas construcciones basadas en celosías se consideran seguras bajo el supuesto de que ciertos problemas de celosía computacional bien estudiados no se pueden resolver de manera eficiente.
Historia
En 1996, Miklós Ajtai introdujo la primera construcción criptográfica basada en celosía cuya seguridad podría basarse en la dureza de problemas de celosía bien estudiados, [1] y Cynthia Dwork mostró que un cierto problema de celosía de casos promedio, conocido como Short Integer Solutions ( SIS), es al menos tan difícil de resolver como un problema de celosía en el peor de los casos . [2] Luego mostró una función hash criptográfica cuya seguridad es equivalente a la dureza computacional de SIS.
En 1998, Jeffrey Hoffstein , Jill Pipher y Joseph H. Silverman introdujeron un esquema de cifrado de clave pública basado en celosía , conocido como NTRU . [3] Sin embargo, no se sabe que su esquema sea al menos tan difícil como resolver un problema de celosía en el peor de los casos.
El primer esquema de cifrado de clave pública basado en celosía cuya seguridad fue probada bajo supuestos de dureza del peor de los casos fue introducido por Oded Regev en 2005, [4] junto con el problema de Aprendizaje con Errores (LWE). Desde entonces, mucho trabajo de seguimiento se ha centrado en mejorar la prueba de seguridad de Regev [5] [6] y mejorar la eficiencia del esquema original. [7] [8] [9] [10] 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 completamente homomórfico , que se basaba en un problema de celosía. [11]
Fondo matemático
Una celosía es el conjunto de todas las combinaciones lineales enteras de vectores básicos . Es decir, Por ejemplo, es una celosía, generada por la base ortonormal estándar para . Fundamentalmente, la base de una celosía no es única. Por ejemplo, los vectores, , y formar una base alternativa para .
El problema de cálculo basado en celosía más importante es el problema del vector más corto (SVP o, a veces, GapSVP), que nos pide aproximar la longitud euclidiana mínima de un vector de celosía distinto de cero. Se cree que este problema es difícil de resolver de manera eficiente, incluso con factores de aproximación que son polinomiales ene incluso con una computadora cuántica. Se sabe que muchas (aunque no todas) construcciones criptográficas basadas en celosías son seguras si SVP es de hecho difícil en este régimen.
Criptosistemas seleccionados basados en celosía
Esquemas de cifrado
- Anillo de Peikert: intercambio de claves de aprendizaje con errores (Ring-LWE) [8]
- Esquema de cifrado GGH
- NTRUEncrypt
Firmas
- Güneysu, Lyubashevsky y el anillo de Poppleman: firma de aprendizaje con errores (Ring-LWE) [12]
- Esquema de firma GGH
- NTRUSign
Funciones hash
Cifrado totalmente homomórfico
Seguridad
Las construcciones criptográficas basadas en celosía son las principales candidatas para la criptografía poscuántica de clave pública . [17] De hecho, las principales formas alternativas de criptografía de clave pública son esquemas basados en la dureza del factoring y problemas relacionados y esquemas basados en la dureza del logaritmo discreto y problemas relacionados . Sin embargo, se sabe que tanto la factorización como el logaritmo discreto se pueden resolver en tiempo polinómico en una computadora cuántica . [18] Además, los algoritmos de factorización tienden a producir algoritmos de logaritmo discreto y viceversa. Esto motiva aún más el estudio de construcciones basadas en supuestos alternativos, como la dureza de los problemas de celosía.
Se sabe que muchos esquemas criptográficos basados en celosías son seguros asumiendo la dureza del peor de los casos de ciertos problemas de celosía. [1] [4] [5] 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 celosía en cualquier entrada. Por el contrario, los esquemas criptográficos basados, por ejemplo, en la factorización se romperían si la factorización fuera fácil "con una entrada promedio ", incluso si la factorización fuera de hecho difícil en el peor de los casos. Sin embargo, para las construcciones más eficientes y prácticas basadas en celosías (como los esquemas basados en NTRU e incluso esquemas basados en LWE con parámetros más agresivos), estos resultados de dureza en el peor de los casos no se conocen. Para algunos esquemas, los resultados de dureza en el peor de los casos se conocen solo para ciertas celosías estructuradas [7] o no en absoluto.
Funcionalidad
Para muchas primitivas criptográficas, las únicas construcciones conocidas se basan en celosías u objetos estrechamente relacionados. Estas primitivas incluyen cifrado totalmente homomórfico , [11] ofuscación de indistinguibilidad , [19] mapas criptográficos multilineales y cifrado funcional . [19]
Ver también
- Problemas de celosía
- Aprendiendo con errores
- Criptografía poscuántica
- Anillo de aprendizaje con errores
- Aprendizaje en anillo con intercambio de claves de errores
Referencias
- ↑ a b Ajtai, Miklós (1996). "Generación de instancias duras de problemas de celosía". Actas del Vigésimo Octavo Simposio Anual ACM sobre Teoría de la Computación . págs. 99–108. CiteSeerX 10.1.1.40.2489 . doi : 10.1145 / 237814.237838 . ISBN 978-0-89791-785-8. S2CID 6864824 .
- ^ Criptosistema de clave pública con equivalencia entre el peor de los casos y el promedio de los casos
- ^ Hoffstein, Jeffrey; Pipher, Jill; Silverman, Joseph H. (1998). "NTRU: un criptosistema de clave pública basado en anillo". Teoría algorítmica de números . Apuntes de conferencias en informática. 1423 . págs. 267–288. CiteSeerX 10.1.1.25.8422 . doi : 10.1007 / bfb0054868 . ISBN 978-3-540-64657-0.
- ^ a b Regev, Oded (1 de enero de 2005). "Sobre celosías, aprendizaje con errores, códigos lineales aleatorios y criptografía". Actas del trigésimo séptimo simposio anual de ACM sobre teoría de la computación - STOC '05 . ACM. págs. 84–93. CiteSeerX 10.1.1.110.4776 . doi : 10.1145 / 1060590.1060603 . ISBN 978-1581139600. S2CID 53223958 .
- ^ a b Peikert, Chris (1 de enero de 2009). "Criptosistemas de clave pública del problema del vector más corto del peor de los casos". Actas del 41º simposio anual de ACM sobre el Simposio sobre teoría de la computación - STOC '09 . ACM. págs. 333–342. CiteSeerX 10.1.1.168.270 . doi : 10.1145 / 1536414.1536461 . ISBN 9781605585062. S2CID 1864880 .
- ^ Brakerski, Zvika; Langlois, Adeline; Peikert, Chris; Regev, Oded; Stehlé, Damien (1 de enero de 2013). "Dureza clásica del aprendizaje con errores". Actas del 45º simposio anual de ACM sobre el Simposio sobre teoría de la computación - STOC '13 . ACM. págs. 575–584. arXiv : 1306.0281 . doi : 10.1145 / 2488608.2488680 . ISBN 9781450320290. S2CID 6005009 .
- ^ a b Lyubashevsky, Vadim; Peikert, Chris; Regev, Oded (30 de mayo de 2010). Sobre entramados ideales y aprendizaje con errores sobre anillos . Avances en Criptología - EUROCRYPT 2010 . Apuntes de conferencias en informática. 6110 . págs. 1–23. CiteSeerX 10.1.1.352.8218 . doi : 10.1007 / 978-3-642-13190-5_1 . ISBN 978-3-642-13189-9.
- ^ a b Peikert, Chris (16 de julio de 2014). "Criptografía de celosía para Internet" (PDF) . IACR . Consultado el 11 de enero de 2017 .
- ^ Alkim, Erdem; Ducas, Léo; Pöppelmann, Thomas; Schwabe, Peter (1 de enero de 2015). "Intercambio de claves post-cuántica - una nueva esperanza" . Cite journal requiere
|journal=
( ayuda ) - ^ Bos, Joppe; Costello, Craig; Ducas, Léo; Mironov, Ilya; Naehrig, Michael; Nikolaenko, Valeria; Raghunathan, Ananth; Stebila, Douglas (1 de enero de 2016). "Frodo: ¡Quítese el anillo! Práctico intercambio de claves Quantum-Secure de LWE" . Cite journal requiere
|journal=
( ayuda ) - ^ a b c Gentry, Craig (1 de enero de 2009). Un esquema de cifrado totalmente homomórfico (tesis). Stanford, CA, EE.UU .: Universidad de Stanford.
- ^ 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 en informática. 7428 . IACR. págs. 530–547. doi : 10.1007 / 978-3-642-33027-8_31 . ISBN 978-3-642-33026-1. Consultado el 11 de enero de 2017 .
- ^ "LASH: una función hash basada en celosía" . Archivado desde el original el 16 de octubre de 2008 . Consultado el 31 de julio de 2008 .CS1 maint: bot: estado de URL original desconocido ( enlace ) (roto)
- ^ Scott Contini, Krystian Matusiewicz, Josef Pieprzyk, Ron Steinfeld, Jian Guo, San Ling y Huaxiong Wang (2008). "Criptoanálisis de LASH" (PDF) . Cifrado de software rápido . Apuntes de conferencias en informática. 5086 . págs. 207–223. doi : 10.1007 / 978-3-540-71039-4_13 . ISBN 978-3-540-71038-7.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Brakerski, Zvika; Vaikuntanathan, Vinod (2011). "Cifrado completamente homomórfico eficiente de (estándar) LWE" . Cite journal requiere
|journal=
( ayuda ) - ^ Brakerski, Zvika; Vaikuntanathan, Vinod (2013). "FHE basado en celosía tan seguro como PKE" . Cite journal requiere
|journal=
( ayuda ) - ^ Micciancio, Daniele; Regev, Oded (22 de julio de 2008). "Criptografía basada en celosía" (PDF) . Consultado el 11 de enero de 2017 . Cite journal requiere
|journal=
( ayuda ) - ^ Shor, Peter W. (1 de octubre de 1997). "Algoritmos de polinomio-tiempo para factorización prima y logaritmos discretos en una computadora cuántica". Revista SIAM de Computación . 26 (5): 1484–1509. arXiv : quant-ph / 9508027 . doi : 10.1137 / S0097539795293172 . ISSN 0097-5397 . S2CID 2337707 .
- ^ a b Garg, Sanjam; Gentry, Craig; Halevi, Shai; Raykova, Mariana; Sahai, Amit; Waters, Brent (1 de enero de 2013). "Ofuscación de indistinguibilidad de candidatos y cifrado funcional para todos los circuitos" . CiteSeerX 10.1.1.400.6501 . Cite journal requiere
|journal=
( ayuda )
Bibliografía
- Oded Goldreich, Shafi Goldwasser y Shai Halevi. "Criptosistemas de clave pública de problemas de reducción de celosía". En CRYPTO '97: Actas de la 17ª Conferencia Anual Internacional de Criptología sobre Avances en Criptología , páginas 112-131, Londres, Reino Unido, 1997. Springer-Verlag.
- Phong Q. Nguyen. "Criptoanálisis del criptosistema Goldreich-Goldwasser-Halevi de crypto '97". En CRYPTO '99: Actas de la 19ª Conferencia Anual Internacional de Criptología sobre Avances en Criptología , páginas 288–304, Londres, Reino Unido, 1999. Springer-Verlag.
- Oded Regev. Criptografía basada en celosía. En Advances in cryptology (CRYPTO) , páginas 131–141, 2006.