Lattice-Based Cryptography in the Quantum Era: A Survey
DOI:
https://doi.org/10.26439/interfases2023.n018.6631Keywords:
post-quantum, lattice-based, quantum computing, kyber, quantum cryptanalysisAbstract
The advent of quantum computing reveals current classical cryptography’s incapacity to withstand attacks within the new paradigm. Quantum algorithms break such encryption with impressive ease, with Shor and Grover algorithms being the main perpetrators. Lattice-based key encryption is the suggested solution in multiple instances, as the complexity and randomness that these methods add to message encryption make them one of the best short- and medium-term solutions. In 2016, NIST launched a contest to find algorithms to incorporate into its security standard. Four algorithms from the third round were selected to be standardized, including the lattice-based CRYSTALSkyber. Of the latter, variants have been and are still being developed that manage to amend some weaknesses found in its implementation, such as side-channel attacks or performance issues. This investigation discusses different publications on lattice-based cryptography in conjunction with cryptanalysis in the quantum era.
Downloads
References
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 Computing. https://www.intel.com/content/www/us/en/newsroom/news/quantum-computing-chip-to-advance-research.html#gs.1o8uud
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
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. (2024). 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
Published
Issue
Section
License
Authors who publish with this journal agree to the following terms:
Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under an Attribution 4.0 International (CC BY 4.0) License. that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
Last updated 03/05/21
