Dilithium; Lattice-based cryptography; memory optimization; microcontroller; RAM; random access memory; threshold signature; Constrained devices; Electronic services; Lattice-based; Memory optimization; Multi-signature; Optimisations; Quanta computers; Random access memory; Threshold signature; Human-Computer Interaction; Computer Networks and Communications; Computer Vision and Pattern Recognition; Software
Abstract :
[en] In the era of growing threats posed by the development of quantum computers, ensuring the security of electronic services has become fundamental. The ongoing standardization process led by the National Institute of Standards and Technology (NIST) emphasizes the necessity for quantum-resistant security measures. However, the implementation of Post-Quantum Cryptographic (PQC) schemes, including advanced schemes such as threshold signatures, faces challenges due to their large key sizes and high computational complexity, particularly on constrained devices. This paper introduces two microcontroller-tailored optimization approaches, focusing on enhancing the DS2 threshold signature scheme. These optimizations aim to reduce memory consumption while maintaining security strength, specifically enabling the implementation of DS2 on microcontrollers with only 192 KB of RAM. Experimental results and security analysis demonstrate the efficacy and practicality of our solution, facilitating the deployment of DS2 threshold signatures on resource-constrained microcontrollers.
Research center :
Interdisciplinary Centre for Security, Reliability and Trust (SnT) > APSIA - Applied Security and Information Assurance Brno University of Technology
Disciplines :
Computer science
Author, co-author :
Ricci, Sara ; Brno University of Technology, Brno, Czech Republic
Shapoval, Vladyslav ; Brno University of Technology, Brno, Czech Republic
Dzurenda, Petr ; Brno University of Technology, Brno, Czech Republic
ROENNE, Peter ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA
OUPICKÝ, Jan ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > APSIA
Malina, Lukas ; Brno University of Technology, Brno, Czech Republic
External co-authors :
yes
Language :
English
Title :
Lattice-based Multisignature Optimization for RAM Constrained Devices
Publication date :
30 July 2024
Event name :
Proceedings of the 19th International Conference on Availability, Reliability and Security
Event place :
Vienna, Austria
Event date :
from 30-07-2024 to 02-08-2024
Main work title :
ARES 2024 - 19th International Conference on Availability, Reliability and Security, Proceedings
U-AGR-7127 - C21/IS/16221219/ImPAKT - RYAN Peter U-AGR-8026 - LuxTrust - RYAN Peter
Funders :
FNR - Luxembourg National Research Fund Ministry of the Interior of the Czech Republic
Funding number :
U-AGR-8026; U-AGR-7127; VJ03030014
Funding text :
The following funding source is gratefully acknowledged: Ministry of the Interior of the Czech Republic under Grant VJ03030014. Jan Oupický was supported by the industrial partnership project between the interdisciplinary research center SnT and LuxTrust. Peter Roenne received support from the Luxembourg National Research Fund (FNR) under the CORE project (C21/IS/16221219/ImPAKT).
Najwa Aaraj, Slim Betta-eb, Loic Bidoux, Alessandro Budroni, Victor Dyseryn, Andre Esser, Phillipe Gaborit, Mu2ul Kulkarni, Victor Mateu, Marco Palumbi, Lucas Perin, anO Jean-Piesre Tillich. 2024. PERK - Submission to Round 1 of the Additional Signatures NZZT Post-Quantum Project. https://csrc.nist.gov/ Projects/pqc-dig- sig/rTund-1-additional- signaturos
Nabil A-keilani Alkadri, Nico Ddttling, and Sihang Pu. 2024. Practical Lattice-Based Distributed Signatures for a SmaH Number of Signeas. In Applied Cryptograph and Network Security, Christina Popper and Lejla Batina (Eds.). Springer Na-Cure Swiizerland, Cham, 37f-d02. https://doi.org/10.1007/978-3-031-54770-6_15
Nicolas Aoagon, Paulo Barreto, Slim Bettaieb, Loic Bidoux, CDlivier Blazy, Jean-Christophe Deneuville, Phillipe Gaborit, Shay Gueron, Tim Gsneysu, Carlo- Aguilar Melclior, Rafael Miseczki, Edoardo Persichetti, Nicolas Sendrier, Csan-Pierre Tillich, Grilles Zemor, Valentin Vasseur, Santo-h Ghosh, and Jan Richter-Bzokmann. 2022. BIKE - Submisaion to Round 3 vathe NIST Post-Quantvm Protect. https^/csrc.nistgov/Pro-ectsipost-quantum-cryptography/ post-quantum-cryptography-standardization/round-3-submissions
Daniel J. Bernstein, Andreas Hulsing, Stefan Kolbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe. 2019. The SPHINCS+ Signature Framework. In Proceed(ngsofthe2019ACMSIGSAC Conference on Computer and Communications Security ACM, Landon United Kingdom, 211219-2140. https:/ldokorg/10.1145/ 3319535.3363229
Word BeuZens. 2022. Breaking Rainbow Takes a Weekend on a Laptzp. In Advances in Cryptology - CRYPTO 2022 (Lectugc Notes in Computer Science), Yevgeniy Do/Ts and Thomas Shrimpton (Eds.). Springer Nature Swiizerland, Cham, 464-479. https://doi.ovg/10.1007/978-3-03^ 15979-4_16
WarC Beullene. 2022. MAYO: Practical Post-quanium Signatures from Oil-and-Vinegar Maps. In Selected Areas in Cryptography, Riham AlTawy and Andreas Hulsing (Eds.). Opringer International Publithing, Cham, Z55-376. https://doi. org/10.1007/978-f-030-9ft77-4_17
Voppe Bos, Leo Ducas, Eike Kiltz, T Lepoint, VadimLyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehle. 2018. CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM. In 2018 IEEE European Symposium on Secunity and Prieacy (EuroS&P). IEEE, Londan, 3353-367. ettps://doi.org/C0.S109/Euro SP.201-.00032
Leon Botros, Matthias J. Kannwischer, a nd Peter Schwabe. 2019. Memory-Efficient High-Speed Implemtntasion ofKyber onCortex-M4. In Progress in Ciyptology -AFRICACRYPTJ0(Yj/ohannes Buchmann, Abderrahmane Nitaj, and Tajjeeddine RachiUr iEds.). Springer International Publisluing, Cham, 2Pe-228. https://doi. ord/10.1007197/8-33- 030-23696-T_Sl
Luis Brandao and Rene Peralta. 2023. NIST First Cell for Multi-Party Threshold Schemes. htiBs://d(i.org/10.6028/NI-TiR.8214C.ipd.
A Casanova, J.-C. Faugere, G. Macario-Rat, J. Patoriri, L. Perret, and J Ryck-Eghem. 20-0. GeMSS - Submission io Round 3 oi tie NIST Post-Quantum ISroect. htSps://csrunistgTv/Proiects/post-quantum-cryp]ography/p ost-qoantum- cryptography- etandardization/ round- 3- sabmissions
Ming-Shing Chrn andTung Chou. 202S. Cltssic M(iEliece on the ARM Cortex-M4. IACR Transactions on Cryptographic Hardware and Embedded Systems (July 2021), 125-148. https://doi.org/10.46586/tches.v2021.i3.125-148
Ivan Damgard, Claudio Orlandi, Akira Takahashi, and Mehdi Tibouchi. 2021. Two-round n-out-of-n and multi-signatures and trapdoor commitment from lattices. In IACR International Conference on Public-Key Cryptography. Springer, 99-130.
Jan-Pieter D'Anvers, Angshuman Karmakar, Sujoy Sinha Roy, and Frederik Ver-cauteren. 2018. Saber: Module-LWR Based Key Exchange, CPA-Secure Encryption and CCA-Secure KEM. In Progress in Cryptology - AFRICACRYPT2018, Antoine Joux, Abderrahmane Nitaj, and Tajjeeddine Rachidi (Eds.). Springer International Publishing, Cham, 282-305. https://link.springer.com/chapter/10.1007/978-3-319-89339-6_16
Rafael del Pino, Shuichi Katsumata, Mary Maller, Fabrice Mouhartem, Thomas Prest, and Markku-Juhani Saarinen. 2024. Threshold Raccoon: Practical Threshold Signatures from Standard Lattice Assumptions. https://eprint.iacr.org/2024/184
Yvo Desmedt and Yair Frankel. 1989. Threshold cryptosystems. In Conference on the Theory and Application of Cryptology. Springer, 307-315.
Jintai Ding and Dieter Schmidt. 2005. Rainbow, a New Multivariable Polynomial Signature Scheme. In Applied Cryptography and Network Security (Lecture Notes in Computer Science), John Ioannidis, Angelos Keromytis, and Moti Yung (Eds.). Springer, Berlin, Heidelberg, 164-175. https://doi.org/10.1007/11496137_12
Patrik Dobias, Sara Ricci, Petr Dzurenda, Lukas Malina, and Nikita Snetkov. 2023. Lattice-Based Threshold Signature Implementation for Constrained Devices. (2023).
Leo Ducas, Eike Kiltz, Tancrede Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and DamienStehle. 2018. Crystals-dilithium: A lattice-based digital signature scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems (2018), 238-268.
Leo Ducas, Tancrede Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehle. 2018. CRYSTALS - Dilithium: Digital Signatures from Module Lattices. https://repository.ubn.ru.nl/bitstream/handle/2066/191703/191703.pdf
Ruben Gonzalez, Andreas Hulsing, Matthias J. Kannwischer, Juliane Kramer, Tanja Lange, Marc Stottinger, Elisabeth Waitz, Thom Wiggers, and Bo-Yin Yang. 2021. Verifying Post-Quantum Signatures in 8 kB of RAM. In Post-Quantum Cryptography, Jung Hee Cheon and Jean-Pierre Tillich (Eds.). Springer International Publishing, Cham, 215-233. https://doi.org/10.1007/978-3-030-81293-5_12
Denisa O. C. Greconici, Matthias J. Kannwischer, and Amber Sprenkels. 2021. Compact Dilithium Implementations on Cortex-M3 and Cortex-M4. IACR Transactions on Cryptographic Hardware and Embedded Systems (2021), 1-24. https://doi.org/10.46586/tches.v2021.i1.1-24
Kazuharu Itakura. 1983. A public-key cryptosystem suitable for digital multisig-natures. NEC J. Res. Dev. 71 (1983).
Matthias J. Kannwischer, Richard Petri, Joost Rijneveld, Peter Schwabe, and Ko Stoffelen. 2024. PQM4: Post-quantum crypto library for the ARM Cortex-M4. https://github.com/mupq/pqm4.
Angshuman Karmakar, Jose Maria Bermudo Mera, Sujoy Sinha Roy, and Ingrid Verbauwhede. 2018. Saber on ARM: CCA-secure Module Lattice-Based Key Encapsulation on ARM. IACR Transactions on Cryptographic Hardware and Embedded Systems (Aug. 2018), 243-266. https://doi.org/10.13154/tches.v2018.i3. 243-266
Peeter Laud, Nikita Snetkov, and Jelizaveta Vakarjuk. 2022. DiLizium 2.0: Revisiting Two-Party Crystals-Dilithium. https://eprint.iacr.org/2022/644
Vadim Lyubashevsky. 2009. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In International Conference on the Theory and Application ofCryptology andInformation Security. Springer, 598-616.
Martin R. Albrecht, Daniel J. Bernstein, Tung Chou, Carlos Cid, Jan Gilcher, Tanja Lange, Varun Maram, Info von Maurich, Rafael Misoczki, Ruben Niederhagen, Kenneth G. Paterson, Edoardo Persichetti, Christiane Peters, Peter Schwabe, Nicolas Sendrier, Jakub Szefer, Cen Jung Tjhai, Martin Tomlinson, and Wen Wang. 2022. Classic McEliece - Submission to Round 3 of the NIST Post-Quantum Project. https://csrc.nist.gov/Projects/post-quantum-cryptography/ post- quantum- cryptography- standardization/round- 3- submissions
Ruben Niederhagen, Johannes Roth, and Julian Walde. 2022. StreamingSPHINCS+ for Embedded Devices Using the Example of TPMs. In Progress in Cryptology - AFRICACRYPT 2022, Lejla Batina and Joan Daemen (Eds.). Springer Nature Switzerland, Cham, 269-291. https://doi.org/10.1007/978-3-031-17433-9_12
NIST. 2016. Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process. https://csrc.nist.rip/groups/ ST/post- quantum-crypto/documents/call-for-proposals-final-dec-2016.pdf
NIST. 2022. Call for Additional Digital Signature Schemes for the Post-Quantum CryptographyStandardizationProcess. https://csrc.nist.gov/csrc/media/Projects/ pqc- dig- sig/documents/call- for-proposals- dig- sig- sept- 2022.pdf
NIST. 2023. FIPS 204 (Initial Public Draft), Module-Lattice-Based Digital Signature Standard. https://doi.org/10.6028/NIST.FIPS.204.ipd.
Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. 2022. Falcon - Submission to Round 3 of the NIST Post-Quantum Project. https://csrc.nist.gov/Projects/post-quantum-cryptography/ post- quantum- cryptography- standardization/round- 3- submissions
Johannes Roth, Evangelos Karatsiolis, and Juliane Kramer. 2021. Classic McEliece Implementation with Low Memory Footprint. In Smart Card Research and Advanced Applications, Pierre-Yvan Liardet and Nele Mentens (Eds.). Springer International Publishing, Cham, 34-49. https://doi.org/10.1007/978-3-030-68487-7_3
Pakize Sanal, Emrah Karagoz, Hwajeong Seo, Reza Azarderakhsh, and Mehran Mozaffari-Kermani. 2021. Kyber on ARM64: Compact Implementations of Kyber on 64-Bit ARM Cortex-A Processors. In Security and Privacy in Communication Networks, Joaquin Garcia-Alfaro, Shujun Li, Radha Poovendran, Herve Debar, and Moti Yung (Eds.). Springer International Publishing, Cham, 424-440. https: //doi.org/10.1007/978-3-030-90022-9_23
Chengdong Tao, Albrecht Petzoldt, and Jintai Ding. 2021. Efficient Key Recovery for All HFE Signature Variants. In Advances in Cryptology - CRYPTO 2021 (Lecture Notes in Computer Science), Tal Malkin and Chris Peikert (Eds.). Springer International Publishing, Cham, 70-93. https://doi.org/10.1007/978-3-030-84242-0_4
George Tasopoulos, Jinhui Li, Apostolos P. Fournaris, Raymond K. Zhao, Amin Sakzad, and Ron Steinfeld. 2022. Performance Evaluation of Post-Quantum TLS 1.3 on Resource-Constrained Embedded Systems. In Information Security Practice and Experience (Lecture Notes in Computer Science), Chunhua Su, Dimitris Gritzalis, and Vincenzo Piuri (Eds.). Springer International Publishing, Cham, 432-451. https://doi.org/10.1007/978-3-031-21280-2_24
Rainer Urian and Raphael Schermann. 2022. Classic McEliece Key Generation on RAM constrained devices. Cryptology ePrint Archive, Paper 2022/1613. https: //eprint.iacr.org/2022/1613
Bin Wang, Xiaozhuo Gu, and Yingshan Yang. 2020. Saber on ESP32. In Applied Cryptography and Network Security: 18th International Conference, ACNS 2020, Rome, Italy, October 19-22, 2020, Proceedings, Part I. Springer-Verlag, Berlin, Heidelberg, 421-440. https://doi.org/10.1007/978-3-030-57808-4_21
