Boolean to arithmetic conversion; Dilithium signature; High-order masking; ML-DSA; Dilithium; High-order; Higher-order; Masking technique; Rejection samplings; Vector sampling; Software; Signal Processing; Hardware and Architecture; Computer Networks and Communications; Computer Graphics and Computer-Aided Design; Artificial Intelligence
Abstract :
[en] In this work, we introduce enhanced high-order masking techniques tailored for Dilithium, the post-quantum signature scheme recently standardized by NIST. We improve the masked generation of the masking vector y, based on a fast Boolean-to-arithmetic conversion modulo q. We also describe an optimized gadget for the high-order masked rejection sampling, with a complexity independent from the size of the modulus q. We prove the security of our gadgets in the classical ISW t-probing model. Finally, we detail our open-source C implementation of these gadgets integrated into a fully masked Dilithium implementation, and provide an efficiency comparison with previous works.
Disciplines :
Computer science
Author, co-author :
CORON, Jean-Sébastien ; University of Luxembourg > Faculty of Science, Technology and Medicine (FSTM) > Department of Computer Science (DCS)
GERARD, François ; University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) > PI Coron
Lepoint, Tancrède; Amazon Web Services, Seattle, United States
Trannoy, Matthias; University of Luxembourg, Esch-sur-Alzette, Luxembourg ; IDEMIA, Cryptography, Courbevoie, France & Security Labs, Courbevoie, France
Zeitoun, Rina; IDEMIA, Cryptography, Courbevoie, France & Security Labs, Courbevoie, France
External co-authors :
yes
Language :
English
Title :
Improved High-Order Masked Generation of Masking Vector and Rejection Sampling in Dilithium
Publication date :
05 September 2024
Journal title :
IACR Transactions on Cryptographic Hardware and Embedded Systems
[ABC+ 23] Melissa Azouaoui, Olivier Bronchain, Gaëtan Cassiers, Clément Hoffmann, Yulia Kuzovkova, Joost Renes, Tobias Schneider, Markus Schönauer, François-Xavier Standaert, and Christine van Vredendaal. Protecting dilithium against leakage revisited sensitivity analysis and improved implementations. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(4):58–79, 2023. https://eprint. iacr.org/2022/1406.
[BBD+ 15] Gilles Barthe, Sonia Belaïd, François Dupressoir, Pierre-Alain Fouque, Benjamin Grégoire, and Pierre-Yves Strub. Verified proofs of higher-order masking. In Advances in Cryptology-EUROCRYPT 2015-Proceedings, Part I, pages 457–485, 2015.
[BBD+ 16] Gilles Barthe, Sonia Belaïd, François Dupressoir, Pierre-Alain Fouque, Benjamin Grégoire, Pierre-Yves Strub, and Rébecca Zucchini. Strong non-interference and type-directed higher-order masking. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24-28, 2016, pages 116–129, 2016. Publicly available at https://eprint.iacr.org/2015/506.pdf.
[BBE+ 18] Gilles Barthe, Sonia Belaïd, Thomas Espitau, Pierre-Alain Fouque, Benjamin Grégoire, Mélissa Rossi, and Mehdi Tibouchi. Masking the GLP lattice-based signature scheme at any order. In Advances in Cryptology-EUROCRYPT 2018-Proceedings, Part II, pages 354–384, 2018.
[BC22] Olivier Bronchain and Gaëtan Cassiers. Bitslicing arithmetic/boolean masking conversions for fun and profit with application to lattice-based kems. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2022(4):553–588, 2022. https://ia. cr/2022/158.
[BCZ18] Luk Bettale, Jean-Sébastien Coron, and Rina Zeitoun. Improved high-order conversion from boolean to arithmetic masking. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2018(2):22–45, 2018.
[BDE+ 18] Jonathan Bootle, Claire Delaplace, Thomas Espitau, Pierre-Alain Fouque, and Mehdi Tibouchi. LWE without modular reduction and improved side-channel attacks against BLISS. In Thomas Peyrin and Steven D. Galbraith, editors, Advances in Cryptology-ASIACRYPT 2018-Proceedings, Part I, volume 11272 of Lecture Notes in Computer Science, pages 494–524. Springer, 2018.
[BDK+ 21] Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyuba-shevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. Crystals-dilithium algorithm specifications and supporting documentation (version 3.1), 2021. https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf.
[CGMZ22] Jean-Sébastien Coron, François Gérard, Simon Montoya, and Rina Zeitoun. High-order table-based conversion algorithms and masking lattice-based en-cryption. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2022(2):1–40, 2022. https://ia.cr/2021/1314.
[CGMZ23] Jean-Sébastien Coron, François Gérard, Simon Montoya, and Rina Zeitoun. High-order polynomial comparison and masking lattice-based encryption. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(1):153–192, 2023. https://ia. cr/2021/1615.
[CGTZ23] Jean-Sébastien Coron, François Gérard, Matthias Trannoy, and Rina Zeitoun. Improved gadgets for the high-order masking of dilithium. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2023(4):110–145, 2023. https://eprint. iacr.org/2023/896.
[CGV14] Jean-Sébastien Coron, Johann Großschädl, and Praveen Kumar Vadnala. Secure conversion between boolean and arithmetic masking of any order. In Proceedings of CHES 2014, pages 188–205, 2014.
[DFPS23] Julien Devevey, Pouria Fallahpour, Alain Passelègue, and Damien Stehlé. A detailed analysis of fiat-shamir with aborts. Cryptology ePrint Archive, Paper 2023/245, 2023. https://eprint.iacr.org/2023/245.
[GLP12] Tim Güneysu, Vadim Lyubashevsky, and Thomas Pöppelmann. Practical lattice-based cryptography: A signature scheme for embedded systems. In Emmanuel Prouff and Patrick Schaumont, editors, Cryptographic Hardware and Embedded Systems – CHES 2012, pages 530–547, Berlin, Heidelberg, 2012. Springer Berlin Heidelberg.
[ISW03] Yuval Ishai, Amit Sahai, and David A. Wagner. Private circuits: Securing hardware against probing attacks. In CRYPTO 2003, Proceedings, pages 463–481, 2003.
[Lyu09] Vadim Lyubashevsky. Fiat-shamir with aborts: Applications to lattice and factoring-based signatures. In Advances in Cryptology–ASIACRYPT 2009: 15th International Conference on the Theory and Application of Cryptology and Information Security, Tokyo, Japan, December 6-10, 2009. Proceedings 15, pages 598–616. Springer, 2009.
[LZS+ 21] Yuejun Liu, Yongbin Zhou, Shuo Sun, Tianyu Wang, Rui Zhang, and Jingdian Ming. On the security of lattice-based fiat-shamir signatures in the presence of randomness leakage. IEEE Trans. Inf. Forensics Secur., 16:1868–1879, 2021.
[MGTF19] Vincent Migliore, Benoît Gérard, Mehdi Tibouchi, and Pierre-Alain Fouque. Masking Dilithium-efficient implementation and side-channel evaluation. In Applied Cryptography and Network Security-17th International Conference, ACNS 2019, Bogota, Colombia, June 5-7, 2019, Proceedings, pages 344–362, 2019.
[MUTS22] Soundes Marzougui, Vincent Ulitzsch, Mehdi Tibouchi, and Jean-Pierre Seifert. Profiling side-channel attacks on dilithium: A small bit-fiddling leak breaks it all. Cryptology ePrint Archive, Paper 2022/106, 2022. https://eprint.iacr. org/2022/106.
[NIS23] NIST. Module-lattice-based digital signature standard. (department of com-merce, washington, d.c.), federal information processing standards publication (fips) nist fips 204 ipd., 2023. https://doi.org/10.6028/NIST.FIPS.204. ipd.
[SPOG19] Tobias Schneider, Clara Paglialonga, Tobias Oder, and Tim Güneysu. Efficiently masking binomial sampling at arbitrary orders for lattice-based crypto. In PKC 2019, Proceedings, Part II, pages 534–564, 2019.
