Scientific and practical cyber security journal | ISSN 2587-4667

POST-QUANTUM DIGITAL SIGNATURE USING VERKLE TREES AND LATTICES

Authors: Maksim Iavich, Tamari Kuchukhidze, Avtandil Gagnidze
Affiliation: Caucasus University, East West University

Category:

Cryptography, cyber security
Keywords: post-quantum cryptography; quantum cryptography; side-channel attacks; CRYSTALS-Kyber; masking; deep-learning; lattice-based cryptography
ABSTRACT. Significant advancements have been achieved in the field of quantum computing in recent years. If somebody ever create a sufficiently strong quantum computer, many of the public key cryptosystems in use today might be compromised. Kyber is a post-quantum encryption technique that depends on lattice problem hardness, and it was recently standardized. Despite extensive testing by the National Institute of Standards and Technology (NIST), new investigations have demonstrated the effectiveness of Crystals-kyber attacks and their applicability in non-controlled environments. We investigated CRYSTALS-Kyber's susceptibility to side-channel attacks. In the reference implementation of Kyber512, additional functions can be compromised by employing the selected ciphertext. The implementation of the selected ciphertext allows the attacks to succeed. Real-time recovery of the entire secret key is possible for all assaults.
 Read full paper

References:

Buchmann, J., Dahmen, E., Szydlo, M. (2009). Hash-based Digital Signature Schemes. In: Bernstein, D.J., Buchmann, J., Dahmen, E. (eds) Post-Quantum Cryptography. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-88702-7_3
Chen, Lily, et al. Report on post-quantum cryptography. Vol. 12. Gaithersburg, MD, USA: US Department of Commerce, National Institute of Standards and Technology, 2016.
Shor, Peter W. "Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer." SIAM review 41, no. 2 (1999): 303-332.
Iavich, Maksim, et al. "ADVANTAGES AND CHALLENGES OF QRNG INTEGRATION INTO MERKLE." Scientific and practical cyber security journal (2020).
Gagnidze, Avtandil, Maksim Iavich, and Giorgi Iashvili. "Novel version of merkle cryptosystem." Bulletin of the Georgian National Academy of Sciences (2017).
Iavich, M., Kuchukhidze, T., & Bocu, R. (2023). A Post-Quantum Digital Signature Using Verkle Trees and Lattices. Symmetry, 15(12), 2165.
Alagic, Gorjan, Daniel Apon, David Cooper, Quynh Dang, Thinh Dang, John Kelsey, Jacob Lichtinger et al. "Status report on the third round of the NIST post-quantum cryptography standardization process." US Department of Commerce, NIST (2022).
Announcing the commercial national security algorithm suite 2.0. National Security Agency, U.S Department of Defense https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF
Avanzi, Roberto, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. "CRYSTALS-Kyber algorithm specifications and supporting documentation." NIST PQC Round 2, no. 4 (2019): 1-43.
Kocher, P., Jaffe, J., Jun, B.: Differential power analysis. In: Annual international cryptology conference. pp. 388–397. Springer (1999)
Wu, L., Perin, G., Picek, S. (2022). On the Evaluation of Deep Learning-Based Side-Channel Analysis. In: Balasch, J., O’Flynn, C. (eds) Constructive Side-Channel Analysis and Secure Design. COSADE 2022. Lecture Notes in Computer Science, vol 13211. Springer, Cham. https://doi.org/10.1007/978-3-030-99766-3_3
Wang, R., Ngo, K., Dubrova, E.: A message recovery attack on LWE/LWR-based PKE/KEMs using amplitude-modulated EM emanations. In: Proc. of 25th Annual Int. Conf. on Information Security and Cryptology (2022), https://eprint.iacr. org/2022/852
Fritzmann, T., Van Beirendonck, M., Basu Roy, D., Karl, P., Schamberger, T., Verbauwhede, I., & Sigl, G. (2021). Masked accelerators and instruction set extensions for post-quantum cryptography. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(1), 414-460.
Gigerl, B., Primas, R., & Mangard, S. (2023, May). Formal verification of arithmetic masking in hardware and software. In International Conference on Applied Cryptography and Network Security (pp. 3-32). Cham: Springer Nature Switzerland
Coron, J. S., Gérard, F., Montoya, S., & Zeitoun, R. (2021). High-order polynomial comparison and masking lattice-based encryption. Cryptology ePrint Archive
Ngo, K., Dubrova, E., Johansson, T.: Breaking masked and shuffled CCA secure Saber KEM by power analysis. In: Proc. of the 5th Workshop on Attacks and Solutions in Hardware Security. pp. 51–61 (2021)
Kairouz, P., McMahan, B., Song, S., Thakkar, O., Thakurta, A., & Xu, Z. (2021, July). Practical and private (deep) learning without sampling or shuffling. In International Conference on Machine Learning (pp. 5213-5225). PMLR.
Nguyen, T. T., Trahay, F., Domke, J., Drozd, A., Vatai, E., Liao, J., ... & Gerofi, B. (2022, May). Why globally re-shuffle? Revisiting data shuffling in large scale deep learning. In 2022 IEEE International Parallel and Distributed Processing Symposium (IPDPS) (pp. 1085-1096). IEEE.
Brisfors, M., Moraitis, M., & Dubrova, E. (2022). Side-channel attack countermeasures based on clock randomization have a fundamental flaw. Cryptology ePrint Archive.
Jayasinghe, D., Udugama, B., & Parameswaran, S. (2023, January). FPGA Based Countermeasures Against Side channel Attacks on Block Ciphers. In Proceedings of the 28th Asia and South Pacific Design Automation Conference (pp. 365-371).
Coron, Jean-Sébastien, and Ilya Kizhvatov. "An efficient method for random delay generation in embedded software." In International Workshop on Cryptographic Hardware and Embedded Systems, pp. 156-170. Berlin, Heidelberg: Springer Berlin Heidelberg, 2009.
Leplus, G., Savry, O., & Bossuet, L. (2022, June). Insertion of random delay with context-aware dummy instructions generator in a RISC-V processor. In 2022 IEEE International Symposium on Hardware Oriented Security and Trust (HOST) (pp. 81-84). IEEE.
Xagawa, K., Ito, A., Ueno, R., Takahashi, J., & Homma, N. (2021). Fault-injection attacks against NIST’s post-quantum cryptography round 3 KEM candidates. In Advances in Cryptology–ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6–10, 2021, Proceedings, Part II 27 (pp. 33-61). Springer International Publishing
Maghrebi, H., Servant, V., & Bringer, J. (2016). There is wisdom in harnessing the strengths of your enemy: Customized encoding to thwart side-channel attacks. In Fast Software Encryption: 23rd International Conference, FSE 2016, Bochum, Germany, March 20-23, 2016, Revised Selected Papers 23 (pp. 223-243). Springer Berlin Heidelberg.
Belleville, N., Couroussé, D., Heydemann, K., & Charles, H. P. (2018). Automated software protection for the masses against side-channel attacks. ACM Transactions on Architecture and Code Optimization (TACO), 15(4), 1-27.
Kreuzer, K. (2023). Verification of Correctness and Security Properties for CRYSTALS-KYBER. Cryptology ePrint Archive.
Wang, Z., Meng, F. H., Park, Y., Eshraghian, J. K., & Lu, W. D. (2023). Side-channel attack analysis on in-memory computing architectures. IEEE Transactions on Emerging Topics in Computing
Moraitis, M., Ji, Y., Brisfors, M., Dubrova, E., & Lindskog, N. (2023). Securing CRYSTALS-Kyber in FPGA Using Duplication and Clock Randomization. IEEE Design & Test.
Jeon, H., Xie, J., Jeon, Y., Jung, K. J., Gupta, A., Chang, W., & Chung, D. (2023). Statistical power analysis for designing bulk, single-cell, and spatial transcriptomics experiments: review, tutorial, and perspectives. Biomolecules, 13(2), 221.
Zulberti, L., Di Matteo, S., Nannipieri, P., Saponara, S., & Fanucci, L. (2022). A script-based cycle-true verification framework to speed-up hardware and software co-design: Performance evaluation on ecc accelerator use-case. Electronics, 11(22), 3704.
Köpf, B., & Dürmuth, M. (2009, July). A provably secure and efficient countermeasure against timing attacks. In 2009 22nd IEEE Computer Security Foundations Symposium (pp. 324-335). IEEE.
He, J., Guo, X., Tehranipoor, M. M., Vassilev, A., & Jin, Y. (2022). EM Side Channels in Hardware Security: Attacks and Defenses. IEEE Des. Test, 39(2), 100-111.
Ricci, S., Dobias, P., Malina, L., Hajny, J., & Jedlicka, P. (2024). Hybrid Keys in Practice: Combining Classical, Quantum and Post-Quantum Cryptography. IEEE Access.
Hofheinz, Dennis, Kathrin Hövelmanns, and Eike Kiltz. "A modular analysis of the Fujisaki-Okamoto transformation." In Theory of Cryptography Conference, pp. 341-371. Cham: Springer International Publishing, 2017.
Kocher, Paul C. "Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems." In Advances in Cryptology—CRYPTO’96: 16th Annual International Cryptology Conference Santa Barbara, California, USA August 18–22, 1996 Proceedings 16, pp. 104-113. Springer Berlin Heidelberg, 1996.
Ngo, Kalle, Elena Dubrova, Qian Guo, and Thomas Johansson. "A side-channel attack on a masked IND-CCA secure saber KEM implementation." IACR Transactions on Cryptographic Hardware and Embedded Systems (2021): 676-707.
Bhasin, Shivam, Jan-Pieter D’Anvers, Daniel Heinz, Thomas Pöppelmann, and Michiel Van Beirendonck. "Attacking and defending masked polynomial comparison for lattice-based cryptography." IACR Transactions on Cryptographic Hardware and Embedded Systems (2021): 334-359.
Guo, Q., Nabokov, D., Nilsson, A., & Johansson, T. (2023, December). Sca-ldpc: A code-based framework for key-recovery side-channel attacks on post-quantum encryption schemes. In International Conference on the Theory and Application of Cryptology and Information Security (pp. 203-236). Singapore: Springer Nature Singapore.
Xu, Zhuang, Owen Pemberton, Sujoy Sinha Roy, David Oswald, Wang Yao, and Zhiming Zheng. "Magnifying side-channel leakage of lattice-based cryptosystems with chosen ciphertexts: The case study of kyber." IEEE Transactions on Computers 71, no. 9 (2021): 2163-2176.
Ravi, Prasanna, Shivam Bhasin, Sujoy Sinha Roy, and Anupam Chattopadhyay. "Drop by Drop you break the rock-Exploiting generic vulnerabilities in Lattice-based PKE/KEMs using EM-based Physical Attacks." IACR Cryptol. ePrint Arch. 2020 (2020): 549.
Beirendonck, Michiel Van, Jan-Pieter D’anvers, Angshuman Karmakar, Josep Balasch, and Ingrid Verbauwhede. "A side-channel-resistant implementation of SABER." ACM Journal on Emerging Technologies in Computing Systems (JETC) 17, no. 2 (2021): 1-26.
Ngo, Kalle, Elena Dubrova, Qian Guo, and Thomas Johansson. "A side-channel attack on a masked IND-CCA secure saber KEM implementation." IACR Transactions on Cryptographic Hardware and Embedded Systems (2021): 676-707.
Bisheh-Niasar, M., Azarderakhsh, R., & Mozaffari-Kermani, M. (2021). Instruction-set accelerated implementation of CRYSTALS-Kyber. IEEE Transactions on Circuits and Systems I: Regular Papers, 68(11), 4648-4659
Di Matteo, S., Sarno, I., & Saponara, S. (2024). CRYPHTOR: A Memory-Unified NTT-Based Hardware Accelerator for Post-Quantum CRYSTALS Algorithms. IEEE Access, 12, 25501-25511.
Nguyen, T. H., Kieu-Do-Nguyen, B., Pham, C. K., & Hoang, T. T. (2024). High-speed NTT Accelerator for CRYSTAL-Kyber and CRYSTAL-Dilithium. IEEE Access.
Wang, H., Zhou, J., Xing, Z., Feng, Q., Zhang, K., Zheng, K., ... & Li, Z. (2023). Fast-convergence digital signal processing for coherent PON using digital SCM. Journal of Lightwave Technology, 41(14), 4635-4643.
Li, L., Qin, G., Yu, Y., & Wang, W. (2023). Compact Instruction Set Extensions for Kyber. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems.
Zhao, Y., Pan, S., Ma, H., Gao, Y., Song, X., He, J., & Jin, Y. (2023). Side channel security oriented evaluation and protection on hardware implementations of kyber. IEEE Transactions on Circuits and Systems I: Regular Papers.
Kundu, S., Karmakar, A., & Verbauwhede, I. (2023, December). On the Masking-Friendly Designs for Post-quantum Cryptography. In International Conference on Security, Privacy, and Applied Cryptography Engineering (pp. 162-184). Cham: Springer Nature Switzerland.
Dubrova, Elena, Kalle Ngo, Joel Gärtner, and Ruize Wang. "Breaking a fifth-order masked implementation of crystals-kyber by copy-paste." In Proceedings of the 10th ACM Asia Public-Key Cryptography Workshop, pp. 10-20. 2023.
Azouaoui, Melissa, Yulia Kuzovkova, Tobias Schneider, and Christine van Vredendaal. "Post-quantum authenticated encryption against chosen-ciphertext side-channel attacks." Cryptology ePrint Archive (2022).
Backlund, Linus, Kalle Ngo, Joel Gärtner, and Elena Dubrova. "Secret Key Recovery Attack on Masked and Shuffled Implementations of CRYSTALS-Kyber and Saber." In International Conference on Applied Cryptography and Network Security, pp. 159-177. Cham: Springer Nature Switzerland, 2023.
Nikova, Svetla, Christian Rechberger, and Vincent Rijmen. "Threshold implementations against side-channel attacks and glitches." In International conference on information and communications security, pp. 529-545. Berlin, Heidelberg: Springer Berlin Heidelberg, 2006.