Provably Secure and Area-Efficient Modular Addition over Boolean Shares
Authors
Guilhèm Assael, Philippe Elbaz-Vincent
Philippe Elbaz-Vincent
Univ. Grenoble Alpes, CNRS, IF, Grenoble, France
philippe dot elbaz-vincent at math dot cnrs dot fr
philippe dot elbaz-vincent at math dot cnrs dot fr
Keywords:
Secure addition over Boolean shares
Robust probing
Area-efficient masking
Lattice-based cryptography
Abstract
Several cryptographic schemes, including lattice-based cryptography and the SHA-2 family of hash functions, involve both integer arithmetic and Boolean logic. Each of these classes of operations, considered separately, can be efficiently implemented under the masking countermeasure when resistance against vertical attacks is required. However, protecting interleaved arithmetic and logic operations is much more expensive, requiring either additional masking conversions to switch between masking schemes, or implementing arithmetic functions as nonlinear operations over a Boolean masking. Both solutions can be achieved by providing masked arithmetic addition over Boolean shares, which is an operation with relatively long latency and usually high area utilization in hardware. A further complication arises when the arithmetic performed by the scheme is over a prime modulus, which is common in lattice-based cryptography. In this work, we propose a first-order masked implementation of arithmetic addition over Boolean shares occupying a very small area, while still having reasonable latency. Our proposal is specifically tuned for efficient addition and subtraction modulo an arbitrary integer, but it can also be configured at runtime for power-of-two arithmetic. To the best of our knowledge, we propose the first such construction whose security is formally proven in the glitch+transition-robust probing model.
References
[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 Jesper Buus Nielsen and Vincent Rijmen, editors, Advances in Cryptology – EUROCRYPT 2018, Part II, volume 10821 of Lecture Notes in Computer Science, pages 354–384. 2018. Springer, Heidelberg. DOI: 10.1007/978-3-319-78375-8_12
[Bed62]
O. J. Bedrij. Carry-Select Adder. IRE Transactions on Electronic Computers, EC-11(3):340–346, 1962. DOI: 10.1109/IRETELC.1962.5407919
[BG22]
Florian Bache and Tim Güneysu. Boolean Masking for Arithmetic Additions at Arbitrary Order in Hardware. Applied Sciences, 12(5), 2022. DOI: 10.3390/app12052274
[BGR+21]
Joppe W. Bos, Marc Gourjon, Joost Renes, Tobias Schneider, and Christine van Vredendaal. Masking Kyber: First- and Higher-Order Implementations. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(4):173–214, 2021. https://tches.iacr.org/index.php/TCHES/article/view/9064 DOI: 10.46586/tches.v2021.i4.173-214
[BMRT22]
Sonia Belaïd, Darius Mercadier, Matthieu Rivain, and Abdul Rahman Taleb. IronMask: Versatile Verification of Masking Security. In 2022 IEEE Symposium on Security and Privacy, pages 142–160. May 2022. IEEE Computer Society Press. DOI: 10.1109/SP46214.2022.9833600
[CFOS21]
Gaëtan Cassiers, Sebastian Faust, Maximilian Orlt, and François-Xavier Standaert. Towards Tight Random Probing Security. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology – CRYPTO 2021, Part III, volume 12827 of Lecture Notes in Computer Science, pages 185–214, Virtual Event. August 2021. Springer, Heidelberg. DOI: 10.1007/978-3-030-84252-9_7
[CGLS21]
Gaëtan Cassiers, Benjamin Grégoire, Itamar Levi, and François-Xavier Standaert. Hardware Private Circuits: From Trivial Composition to Full Verification. IEEE Transactions on Computers, 70(10):1677–1690, 2021. DOI: 10.1109/TC.2020.3022979
[CGM+23]
Gaëtan Cassiers, Barbara Gigerl, Stefan Mangard, Charles Momin, and Rishub Nagpal. Compress: Reducing Area and Latency of Masked Pipelined Circuits. https://eprint.iacr.org/2023/1600. Cryptology ePrint Archive, Report 2023/1600. 2023.
[CGV14]
Jean-Sébastien Coron, Johann Großschädl, and Praveen Kumar Vadnala. Secure Conversion between Boolean and Arithmetic Masking of Any Order. In Lejla Batina and Matthew Robshaw, editors, Cryptographic Hardware and Embedded Systems – CHES 2014, volume 8731 of Lecture Notes in Computer Science, pages 188–205. September 2014. Springer, Heidelberg. DOI: 10.1007/978-3-662-44709-3_11
[CJRR99]
Suresh Chari, Charanjit S. Jutla, Josyula R. Rao, and Pankaj Rohatgi. Towards Sound Approaches to Counteract Power-Analysis Attacks. In Michael J. Wiener, editor, Advances in Cryptology – CRYPTO'99, volume 1666 of Lecture Notes in Computer Science, pages 398–412. August 1999. Springer, Heidelberg. DOI: 10.1007/3-540-48405-1_26
[CMM+23]
Gaëtan Cassiers, Loïc Masure, Charles Momin, Thorben Moos, Amir Moradi, and François-Xavier Standaert. Randomness Generation for Secure Hardware Masking – Unrolled Trivium to the Rescue. Cryptology ePrint Archive, Paper 2023/1134. 2023.
[CS20]
Gaëtan Cassiers and François-Xavier Standaert. Trivially and Efficiently Composing Masked Gadgets With Probe Isolating Non-Interference. IEEE Transactions on Information Forensics and Security, 15:2542-2555, 2020. DOI: 10.1109/TIFS.2020.2971153
[CS21]
Gaëtan Cassiers and François-Xavier Standaert. Provably Secure Hardware Masking in the Transition- and Glitch-Robust Probing Model: Better Safe than Sorry. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2021(2):136–158, 2021. https://tches.iacr.org/index.php/TCHES/article/view/8790 DOI: 10.46586/tches.v2021.i2.136-158
[DDF14]
Alexandre Duc, Stefan Dziembowski, and Sebastian Faust. Unifying Leakage Models: From Probing Attacks to Noisy Leakage. In Phong Q. Nguyen and Elisabeth Oswald, editors, Advances in Cryptology – EUROCRYPT 2014, volume 8441 of Lecture Notes in Computer Science, pages 423–440. May 2014. Springer, Heidelberg. DOI: 10.1007/978-3-642-55220-5_24
[DZD+18]
A. Adam Ding, Liwei Zhang, François Durvaux, François-Xavier Standaert, and Yunsi Fei. Towards sound and optimal leakage detection procedure. In Smart Card Research and Advanced Applications: 16th International Conference, CARDIS 2017, Lugano, Switzerland, November 13–15, 2017, Revised Selected Papers, pages 105–122, Cham. 2018. Springer. DOI: 10.1007/978-3-319-75208-2_7
[FBR+22]
Tim Fritzmann, Michiel Van Beirendonck, Debapriya Basu Roy, Patrick Karl, Thomas Schamberger, Ingrid Verbauwhede, and Georg Sigl. Masked Accelerators and Instruction Set Extensions for Post-Quantum Cryptography. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(1):414–460, 2022. DOI: 10.46586/tches.v2022.i1.414-460
[FG05]
Wieland Fischer and Berndt M. Gammel. Masking at Gate Level in the Presence of Glitches. In Josyula R. Rao and Berk Sunar, editors, Cryptographic Hardware and Embedded Systems – CHES 2005, volume 3659 of Lecture Notes in Computer Science, pages 187–200. 2005. Springer, Heidelberg. DOI: 10.1007/11545262_14
[FGP+18]
Sebastian Faust, Vincent Grosso, Santos Merino Del Pozo, Clara Paglialonga, and François-Xavier Standaert. Composable Masking Schemes in the Presence of Physical Defaults & the Robust Probing Model. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(3):89–120, 2018. https://tches.iacr.org/index.php/TCHES/article/view/7270 DOI: 10.13154/tches.v2018.i3.89-120
[FIP23a]
Module-Lattice-Based Key-Encapsulation Mechanism. National Institute of Standards and Technology, draft of NIST FIPS PUB 203, U.S. Department of Commerce. August 2023.
[FIP23b]
Module-Lattice-Based Digital Signature Standard. National Institute of Standards and Technology, draft of NIST FIPS PUB 204, U.S. Department of Commerce. August 2023.
[GJJR11]
Gilbert Goodwill, Benjamin Jun, Josh Jaffe, and Pankaj Rohatgi. A testing methodology for side-channel resistance validation. In NIST non-invasive attack testing workshop, volume 7, pages 115–136. 2011. Cryptography Research Inc..
[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, volume 2162 of Lecture Notes in Computer Science, pages 3–15. May 2001. Springer, Heidelberg. DOI: 10.1007/3-540-44709-1_2
[ISW03]
Yuval Ishai, Amit Sahai, and David Wagner. Private Circuits: Securing Hardware against Probing Attacks. In Dan Boneh, editor, Advances in Cryptology – CRYPTO 2003, volume 2729 of Lecture Notes in Computer Science, pages 463–481. August 2003. Springer, Heidelberg. DOI: 10.1007/978-3-540-45146-4_27
[KM22]
David Knichel and Amir Moradi. Low-Latency Hardware Private Circuits. In Heng Yin, Angelos Stavrou, Cas Cremers, and Elaine Shi, editors, ACM CCS 2022: 29th Conference on Computer and Communications Security, pages 1799–1812. November 2022. ACM Press. DOI: 10.1145/3548606.3559362
[KSM20]
David Knichel, Pascal Sasdrich, and Amir Moradi. SILVER - Statistical Independence and Leakage Verification. In Shiho Moriai and Huaxiong Wang, editors, Advances in Cryptology – ASIACRYPT 2020, Part I, volume 12491 of Lecture Notes in Computer Science, pages 787–816. December 2020. Springer, Heidelberg. DOI: 10.1007/978-3-030-64837-4_26
[KSWH98]
John Kelsey, Bruce Schneier, David Wagner, and Chris Hall. Side Channel Cryptanalysis of Product Ciphers. In Jean-Jacques Quisquater, Yves Deswarte, Catherine Meadows, and Dieter Gollmann, editors, ESORICS'98: 5th European Symposium on Research in Computer Security, volume 1485 of Lecture Notes in Computer Science, pages 97–110. September 1998. Springer, Heidelberg. DOI: 10.1007/BFb0055858
[LB61]
M. Lehman and N. Burla. Skip Techniques for High-Speed Carry-Propagation in Binary Arithmetic Units. IRE Transactions on Electronic Computers, EC-10(4):691–698, 1961. DOI: 10.1109/TEC.1961.5219274
[LDK+20]
Vadim Lyubashevsky, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Peter Schwabe, Gregor Seiler, Damien Stehlé, and Shi Bai. CRYSTALS-DILITHIUM. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
[Mac61]
O. L. MacSorley. High-Speed Arithmetic in Binary Computers. Proceedings of the IRE, 49(1):67–91, 1961. DOI: 10.1109/JRPROC.1961.287779
[PR13]
Emmanuel Prouff and Matthieu Rivain. Masking against Side-Channel Attacks: A Formal Security Proof. In Thomas Johansson and Phong Q. Nguyen, editors, Advances in Cryptology – EUROCRYPT 2013, volume 7881 of Lecture Notes in Computer Science, pages 142–159. May 2013. Springer, Heidelberg. DOI: 10.1007/978-3-642-38348-9_9
[SAB+20]
Peter Schwabe, Roberto Avanzi, Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Gregor Seiler, and Damien Stehlé. CRYSTALS-KYBER. Technical report, National Institute of Standards and Technology. available at https://csrc.nist.gov/projects/post-quantum-cryptography/post-quantum-cryptography-standardization/round-3-submissions. 2020.
[Skl60]
Jack Sklansky. Conditional-Sum Addition Logic. IRE Transactions on Electronic Computers, EC-9(2):226–231, 1960. DOI: 10.1109/TEC.1960.5219822
[SMG15]
Tobias Schneider, Amir Moradi, and Tim Güneysu. Arithmetic Addition over Boolean Masking – Towards First- and Second-Order Resistance in Hardware. In Tal Malkin, Vladimir Kolesnikov, Allison Bishop Lewko, and Michalis Polychronakis, editors, ACNS 15: 13th International Conference on Applied Cryptography and Network Security, volume 9092 of Lecture Notes in Computer Science, pages 559–578. June 2015. Springer, Heidelberg. DOI: 10.1007/978-3-319-28166-7_27
[SMRM19]
Rajat Sadhukhan, Paulson Mathew, Debapriya Basu Roy, and Debdeep Mukhopadhyay. Count Your Toggles: a New Leakage Model for Pre-Silicon Power Analysis of Crypto Designs. Journal of Electronic Testing, 35(5):605–619, 2019. DOI: 10.1007/s10836-019-05826-8
[WT90]
B.W.Y. Wei and C.D. Thompson. Area-time optimal adder design. IEEE Transactions on Computers, 39(5):666–675, 1990. DOI: 10.1109/12.53579
PDF
History
Submitted: 2024-04-08
Accepted: 2024-06-03
Published: 2024-07-08
Accepted: 2024-06-03
Published: 2024-07-08
How to cite
Guilhèm Assael and Philippe Elbaz-Vincent, "Provably Secure and Area-Efficient Modular Addition over Boolean Shares," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/aee0zoja5.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.