Dilithium; high-order masking; Lattice-based signature; High-order; High-order masking; Higher-order; Lattice-based; National Institute of Standards and Technology; Post quantum; Quantum signature; Shift-and; Signature Scheme; Software; Signal Processing; Hardware and Architecture; Computer Networks and Communications; Computer Graphics and Computer-Aided Design; Artificial Intelligence
Abstract :
[en] We present novel and improved high-order masking gadgets for Dilithium, a post-quantum signature scheme that has been standardized by the National Institute of Standards and Technologies (NIST). Our proposed gadgets include the ShiftMod gadget, which is used for efficient arithmetic shifts and serves as a component in other masking gadgets. Additionally, we propose a new algorithm for Boolean-to-arithmetic masking conversion of a µ-bit integer x modulo any integer q, with a complexity that is independent of both µ and q. This algorithm is used in Dilithium to mask the generation of the random variable y modulo q. Moreover, we describe improved techniques for masking the Decompose function in Dilithium. Our new gadgets are proven to be secure in the t-probing model. We demonstrate the effectiveness of our countermeasures by presenting a complete high-order masked implementation of Dilithium that utilizes the improved gadgets described above. We provide practical results obtained from a C implementation and compare the performance improvements provided by our new gadgets with those of previous work.
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
Trannoy, Matthias; University of Luxembourg, Esch-sur-Alzette, Luxembourg ; IDEMIA, Cryptography & Security Labs, Courbevoie, France
Zeitoun, Rina; IDEMIA, Cryptography & Security Labs, Courbevoie, France
External co-authors :
yes
Language :
English
Title :
Improved Gadgets for the High-Order Masking of Dilithium
Publication date :
31 August 2023
Event name :
CHES 2023
Event date :
September 2023
Journal title :
IACR Transactions on Cryptographic Hardware and Embedded Systems
[ABC+22] Melissa Azouaoui, Olivier Bronchain, Gaëtan Cassiers, Clément Hoffmann, Yulia Kuzovkova, Joost Renes, Markus Schönauer, Tobias Schneider, FrançoisXavier Standaert, and Christine van Vredendaal. Leveling dilithium against leakage: Revisited sensitivity analysis and improved implementations. Cryptology ePrint Archive, Paper 2022/1406, 2022. 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 noninterference 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-24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part I, volume 11272 of Lecture Notes in Computer Science, pages 494–524. Springer, 2018.
[BDH+21] Shivam Bhasin, Jan-Pieter D’Anvers, Daniel Heinz, Thomas Pöppelmann, and Michiel Van Beirendonck. Attacking and defending masked polynomial comparison for lattice-based cryptography. IACR Trans. Cryptogr. Hardw. Embed. Syst., 2021(3):334–359, 2021. https://eprint.iacr.org/2021/104.
[BDK+21] Shi Bai, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. Crystalsdilithium algorithm specifications and supporting documentation (version 3.1), 2021. https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf.
[BG14] Shi Bai and Steven D. Galbraith. An improved compression technique for signatures based on learning with errors. In Josh Benaloh, editor, Topics in Cryptology – CT-RSA 2014, pages 28–47, Cham, 2014. Springer International Publishing.
[CGMZ22] Jean-Sébastien Coron, François Gérard, Simon Montoya, and Rina Zeitoun. High-order table-based conversion algorithms and masking lattice-based encryption. 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.
[CGTV15] Jean-Sébastien Coron, Johann Großschädl, Mehdi Tibouchi, and Praveen Kumar Vadnala. Conversion from arithmetic to boolean masking with logarithmic complexity. In Proceedings of FSE 2015, pages 130–149, 2015.
[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.
[Cor14] Jean-Sébastien Coron. Higher order masking of look-up tables. In Proceedings of EUROCRYPT 2014, pages 441–458, 2014.
[CS21] Jean-Sébastien Coron and Lorenzo Spignoli. Secure wire shuffling in the probing model. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology CRYPTO 2021-41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part III, volume 12827 of Lecture Notes in Computer Science, pages 215–244. Springer, 2021.
[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.
[Gou01] Louis Goubin. A sound method for switching between boolean and arithmetic masking. In Çetin Kaya Koç, David Naccache, and Christof Paar, editors, Cryptographic Hardware and Embedded Systems-CHES 2001, Third International Workshop, Paris, France, May 14-16, 2001, Proceedings, volume 2162 of Lecture Notes in Computer Science, pages 3–15. Springer, 2001.
[ISW03] Yuval Ishai, Amit Sahai, and David A. Wagner. Private circuits: Securing hardware against probing attacks. In CRYPTO 2003, Proceedings, pages 463–481, 2003.
[LS15] Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr., 75(3):565–599, 2015.
[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.
[RP10] Matthieu Rivain and Emmanuel Prouff. Provably secure higher-order masking of AES. In CHES 2010, Proceedings, pages 413–427, 2010.
[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.
