Criptografía lattice-based en la era cuántica: una revisión
Resumen
La llegada de la informática cuántica anuncia la inadecuación de la criptografía clásica actual para resistir los ataques dentro de este nuevo paradigma. Los algoritmos cuánticos rompen este tipo de cifrado con una facilidad impresionante, siendo los algoritmos de Shor y Grover los principales culpables. El cifrado de claves basado en celosías es la solución propuesta en múltiples ocasiones, ya que la complejidad y aleatoriedad añadidas al cifrado de mensajes mediante estos métodos los convierten en una de las mejores soluciones a corto y medio plazo. En 2016, el NIST lanzó un concurso para encontrar los algoritmos que formarán parte del estándar de seguridad, y en la tercera ronda se seleccionaron cuatro algoritmo para ser estandarizados, entre ellos uno basado en celosía, CRYSTALS-kyber. A partir de él, se desarrollaron y se están desarrollando variantes que consiguen solventar algunas debilidades encontradas en la implementación, como ataques de canal lateral o problemas de rendimiento. En la presente investigación se discuten diferentes publicaciones relativas a la criptografía basada en celosías en conjunción con el criptoanálisis en la era cuántica.
Descargas
Citas
Aaronson, S., & Chen, L. Q. (2017). Complexity-theoretic foundations of quantum supremacy experiments. Quantum Physics, 67. https://doi.org/10.5555/3135595.3135617
Allende, M., León, D. L., Cerón, S., Pareja, A., Pacheco, E., Leal, A., Da Silva, M., Pardo, A., Jones, D., Worrall, D. J., Merriman, B., Gilmore, J., Kitchener, N., & Venegas-Andraca, S. E. (2023). Quantum-resistance in blockchain networks. Scientific Reports, 13(1). https://doi.org/10.1038/s41598-023-32701-6
Alkim, E., Bindel, N., Buchmann, J., Dagdelen, Ö., Eaton, E., Gutoski, G., Krämer, J., & Pawlega, F. (2015). Revisiting TESLA in the quantum random oracle model. Cryptology ePrint Archive, Paper 2015/755. https://eprint.iacr.org/2015/755
Alkim, E., Bos, J. W., Ducas, L., Easterbrook, K., LaMacchia, B., Longa, P., Mironov, I., Naehrig, M., Nikolaenko, V., Peikert, C., Raghunathan, A., & Stebila, D. (2020). FrodoKEM: Learning with errors key encapsulation. https://frodokem.org/.
Alyami, H., Nadeem, M., Alosaimi, W., Alharbi, A. G., Kumar, R., Gupta, B. K., Agrawal, A., & Khan, R. A. (2022). Analyzing the Data of Software Security Life-Span: Quantum Computing Era. Intelligent Automation Soft Computing, 31(2), 707-716. https://doi.org/10.32604/iasc.2022.020780
Arute, F., Arya, K., Babbush, R., Bacon, D., Bardin, J. C., Barends, R., Biswas, R., Boixo, S., Brandão, F. G. S. L., Buell, D. A., Burkett, B. J., Chen, Y., Chen, Z., Chiaro, B., Collins, R., Courtney, W., Dunsworth, A., Farhi, E., Foxen, B., . . . Martinis, J. M. (2019). Quantum supremacy using a programmable superconducting processor. Nature, 574(7779), 505-510. https://doi.org/10.1038/s41586-019-1666-5
Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehlé, D. (2020). Algorithm Specifications And Supporting Documentation. NIST Report.
Banegas, G. (2020). Concrete quantum cryptanalysis of binary elliptic curves. https://ia.cr/2020/1296
Benioff, P. (1980). The computer as a physical system: A microscopic quantum mechanical Hamiltonian model of computers as represented by Turing machines. Journal of Statistical Physics, 22(5), 563-591. https://doi.org/10.1007/bf01011339
Bernstein, D., Buchmann, J., & Dahmen, E. (2017). Post-quantum cryptography. Nature, 549(7671), 188-194. https://doi.org/10.1038/nature23461
Bernstein, D. J., Chuengsatiansup, C., Lange, T., & Van Vredendaal, C. (2016). NTRU Prime: reducing attack surface at low cost. Cryptology ePrint Archive, Paper 2016/461. https://eprint.iacr.org/2016/461
Bos, J. W., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., & Stehlé, D. (2018). CRYSTALS - Kyber: A CCA-Secure Module-Lattice- Based KEM. https://doi.org/10.1109/eurosp.2018.00032
Cheon, J. H., Park, S., Lee, J., Kim, D., Song, Y., Hong, S., Kim, D., Kim, J., Hong, S. M., Yun, A., Kim, J., Park, H., Choi, E., Kim, K., Kim, J., & Lee, J. (2017). Lizard. Lizard Public Key Encryption Submission to NIST proposal. National Institute of Standards and Technology.
Chen, S., & Chen, J. (2023). Lattice-based group signatures with forward security for anonymous authentication. Heliyon, 9(4). Elsevier BV. https://doi.org/10.1016/j.heliyon.2023.e14917
Cho, A. C. (2023, June 25). Ordinary computers can beat Google’s quantum computer after all. Science | AAAS. https://www.science.org/content/article/ ordinary-computers-can-beat-google-s-quantum-computer-after-all
D’Anvers, J., Karmakar, A., Roy, S. S., & Vercauteren, F. (2018). Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM. En Progress in Cryptology - AFRICACRYPT 2018 (pp. 282-305). Springer eBooks. https://doi.org/10.1007/978-3-319-89339-6_16
Ding, J., Kudo, M., Okumura, S., Takagi, T., & Tao, C. (2018). Cryptanalysis of a public key cryptosystem based on Diophantine equations via weighted LLL reduction. Japan Journal of Industrial and Applied Mathematics, 35(3), 1123-1152. https://doi.org/10.1007/s13160-018-0316-x
Ducas, L., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., & Stehle, D. (2017). CRYSTALS - Dilithium: Digital Signatures from Module Lattices. Cryptology ePrint Archive, Paper 2017/633. https://eprint.iacr.org/2017/633
Hekkala, J., Muurman, M., Halunen, K., & Vallivaara, V. (2023). Implementing Postquantum Cryptography for Developers. In SN Computer Science (vol. 4). Springer Science and Business Media LLC. https://doi.org/10.1007/s42979-023-01724-1
Hülsing, A., Rijneveld, J., Schanck, J. M., & Schwabe, P. (2017). High-speed key encapsulation from NTRU. Cryptology ePrint Archive, Paper 2017/667. https://eprint.iacr.org/2017/667
Intel. (2023, June 15). Intel’s New Chip to Advance Silicon Spin Qubit Research for Quantum
Jaques, S., & Schanck, J. M. (2019). Quantum Cryptanalysis in the RAM Model: Claw-Finding Attacks on SIKE. En Lecture Notes in Computer Science (pp. 32-61). Springer Science+Business Media. https://doi.org/10.1007/978-3-030-26948-7_2
Jing, Z., Gu, C., Ge, C., & Shi, P. (2020). Cryptanalysis of a Public Key Cryptosystem Based on
Data Complexity under Quantum Environment. Mobile Networks and Applications. https://doi.org/10.1007/s11036-019-01498-y
Kobayashi, T., Nakajima, T., Takeda, K., Noiri, A., Yoneda, J., & Tarucha, S. (2023). Feedbackbased
active reset of a spin qubit in silicon. Npj Quantum Information, 9(1). https://doi.org/10.1038/s41534-023-00719-3
Kumari, S., Singh, M., Singh, R. P., & Tewari, H. (2022). A post-quantum lattice based lightweight authentication and code-based hybrid encryption scheme for IoT devices. Computer Networks, 217, 109327. https://doi.org/10.1016/j.comnet.2022.109327
Liu, Y., Arunachalam, S., & Temme, K. (2021). A rigorous and robust quantum speed-up in supervised machine learning. Nature Physics, 17(9), 1013-1017. https://doi.org/10.1038/s41567-021-01287-z
Mavroeidis, V., Vishi, K., Zych, M., & Jøsang, A. (2018). The Impact of Quantum Computing on Present Cryptography. International Journal of Advanced Computer Science and Applications, 9(3). https://doi.org/10.14569/ijacsa.2018.090354
Moody, D. (2022). Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process. https://doi.org/10.6028/nist.ir.8413-upd1
Mor, T., & Renner, R. (2014). Preface. Natural Computing, 13(4), 447-452. https://doi.org/10.1007/s11047-014-9464-3
Nejatollahi, H., Dutt, N., Ray, S., Regazzoni, F., Banerjee, I., & Cammarota, R. (2019). Post-
Quantum Lattice-Based Cryptography Implementations. ACM Computing Surveys, 51(6), 1-41. https://doi.org/10.1145/3292548
Riel, H. (2022). Quantum Computing Technology and Roadmap. https://doi.org/10.1109/essderc55479.2022.9947181
Roman’kov, V., Ushakov, A., & Shpilrain, V. (2023). Algebraic and quantum attacks on two digital signature schemes. En Journal of Mathematical Cryptology (vol. 17). Walter de Gruyter GmbH. https://doi.org/10.1515/jmc-2022-0023
Sammons, A., & Putwain, D. (2018). Psychology and Crime (2.a ed.). Routledge Saarinen, M.-J. O. (2017). HILA5: On Reliability, Reconciliation, and Error Correction for Ring- LWE Encryption. Cryptology ePrint Archive, Paper 2017/424. https://eprint.iacr.org/2017/424
Schumacher, B. (1995). Quantum coding. Physical Review A, 51(4), 2738-2747. https://doi.org/10.1103/physreva.51.2738
Schwabe, P., & Westerbaan, B. (2016). Solving Binary {MQ with Grover’s Algorithm. In Lecture Notes in Computer Science (pp. 303-322). Springer Science+Business Media. https://doi.org/10.1007/978-3-319-49445-6_17
Seck, B., Cayrel, P., Diop, I., & Barbier, M. (2022). Cryptanalysis of a Code-Based Identification Scheme Presented in CANS 2018. En Communications in computer and information science (pp. 3-19). Springer Science+Business Media. https://doi.org/10.1007/978-3-031-23201-5_1
Soni, L., Chandra, H., Gupta, D., & Keval, R. (2022). Quantum-resistant public-key encryption and signature schemes with smaller key sizes. Cluster Computing. https://doi.org/10.1007/s10586-022-03955-y
Ura, K., Imoto, T., Nikuni, T., Kawabata, S., & Matsuzaki, Y. (2023). Analysis of the shortest vector problems with quantum annealing to search the excited states. In Japanese Journal of Applied Physics (vol. 62). IOP Publishing. https://doi.org/10.35848/1347-4065/acba21
Vaishnavi, A., & Pillai, S. (2021). Cybersecurity in the Quantum Era-A Study of Perceived Risks in Conventional Cryptography and Discussion on Post Quantum Methods. Journal of Physics, 1964(4). https://doi.org/10.1088/1742-6596/1964/4/042002
Wang, Y., & Zhang, H. (2021). Quantum Algorithm for Attacking RSA Based on Fourier Transform and Fixed-Point. Wuhan University Journal of Natural Sciences, 26(6), 489-494. https://doi.org/10.1051/wujns/2021266489
Xiao, K., Chen, X., Huang, J., Li, H., & Huang, Q. (2023). A lattice-based public key encryption scheme with delegated equality test. Computer Standards & Interfaces, 87. https://doi.org/10.1016/j.csi.2023.103758
Xie, H., & Yang, L. (2019). Using Bernstein–Vazirani algorithm to attack block ciphers. Designs, Codes and Cryptography, 87(5), 1161-1182. https://doi.org/10.1007/s10623-018-0510-5
Yang, N., Yang, S., Zhao, Y., Wu, W., & Wang, X. (2023). Inner product encryption from Middle Product Learning With Errors. Computer Standards & Interfaces, 87. https://doi.org/10.1016/j.csi.2023.103755
Yang, Y., Wang, Z., Ye, J., Fan, J., Chen, S., Li, H., Li, X., & Cao, Y. (2023). Chosen ciphertext correlation power analysis on Kyber. Integration, 91, 10-22. https://doi.org/10.1016/j.vlsi.2023.02.012
Zeydan, E., Turk, Y., Aksoy, B., & Ozturk, S. B. (2022). Recent Advances in Post-Quantum Cryptography for Networks: A Survey. In 2022 Seventh International Conference On Mobile And Secure Services (pp. 1-8). IEEE. https://doi.org/10.1109/mobisecserv50855.2022.9727214
Zhilong, J., Fu, Y., Cao, Z., Cheng, W., Zhao, Y., Dou, M., Duan, P., Kong, W., Cao, G., Li, H., & Guo, G. (2022). Superconducting and Silicon-Based Semiconductor Quantum Computers: A review. IEEE Nanotechnology Magazine, 16(4), 10-19. https://doi.org/10.1109/mnano.2022.3175394
Los autores/as que publiquen en esta revista aceptan las siguientes condiciones:
Los autores/as conservan los derechos de autor y ceden a la revista el derecho de la primera publicación, con el trabajo registrado con la licencia de atribución de Creative Commons, que permite a terceros utilizar lo publicado siempre que mencionen la autoría del trabajo y a la primera publicación en esta revista.
Los autores/as pueden realizar otros acuerdos contractuales independientes y adicionales para la distribución no exclusiva de la versión del artículo publicado en esta revista (p. ej., incluirlo en un repositorio institucional o publicarlo en un libro) siempre que indiquen claramente que el trabajo se publicó por primera vez en esta revista.
Se permite y recomienda a los autores/as a publicar su trabajo en Internet (por ejemplo en páginas institucionales o personales) antes y durante el proceso de revisión y publicación, ya que puede conducir a intercambios productivos y a una mayor y más rápida difusión del trabajo publicado (vea The Effect of Open Access).
Última actualización: 03/05/21