Masked Computation of the Floor Function and Its Application to the FALCON Signature

Pierre-Augustin Berthet; Justine Paillet; Cédric Tavernier; Lilian Bossuet; Brice Colombier

doi:10.62056/ay73zl7s

Masked Computation of the Floor Function and Its Application to the FALCON Signature

Authors

Pierre-Augustin Berthet, Justine Paillet, Cédric Tavernier, Lilian Bossuet, Brice Colombier

Pierre-Augustin Berthet

Institut Polytechnique de Paris, Palaiseau, France
Hensoldt France SAS, Plaisir, France
berthet at telecom-paris dot fr

Justine Paillet

Université Jean-Monnet Saint-Étienne, Saint-Étienne, France
Hensoldt France SAS, Plaisir, France
justine dot paillet at univ-st-etienne dot fr

Cédric Tavernier

Hensoldt France SAS, Plaisir, France
cedric dot tavernier at hensoldt dot net

Lilian Bossuet

Université Jean-Monnet Saint-Étienne, Saint-Étienne, France
lilian dot bossuet at univ-st-etienne dot fr

Brice Colombier

Université Jean-Monnet Saint-Étienne, Saint-Étienne, France
b dot colombier at univ-st-etienne dot fr

Abstract

FALCON is a signature selected for standardisation of the new Post-Quantum Cryptography (PQC) primitives by the National Institute of Standards and Technology (NIST). However, it remains a challenge to define efficient countermeasures against side-channel attacks (SCA) for this algorithm. FALCON is a lattice-based signature that relies on rational numbers, which is unusual in the cryptography field. Although recent work proposed a solution to mask the addition and the multiplication, some roadblocks remain, most noticeably, how to protect the floor function. In this work, we propose to complete the first existing tests of hardening FALCON against SCA. We perform the mathematical proofs of our methods as well as formal security proofs in the probing model by ensuring Multiple Input Multiple Output Strong Non-Interference (MIMO-SNI) security. We provide performances on a laptop computer of our gadgets as well as of a complete masked FALCON. We notice significant overhead in doing so and discuss the deployability of our method in a real-world context.

References

[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, pages 116–129, New York, NY, USA. 2016. Association for Computing Machinery. DOI: 10.1145/2976749.2978427

Google Scholar ePrint

[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, Tel Aviv, Israel. April 29 – May 3, 2018. Springer, Cham, Switzerland. DOI: 10.1007/978-3-319-78375-8_12

Google Scholar ePrint

[BCZ18]

Luk Bettale, Jean-Sébastien Coron, and Rina Zeitoun. Improved High-Order Conversion From Boolean to Arithmetic Masking. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(2):22–45, May 2018. DOI: 10.13154/tches.v2018.i2.22-45

Google Scholar ePrint

[BDK⁺18]

Joppe Bos, Leo Ducas, Eike Kiltz, T Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehle. CRYSTALS - Kyber: A CCA-Secure Module-Lattice-Based KEM. In 2018 IEEE European Symposium on Security and Privacy (EuroS&P), pages 353-367. April 2018. DOI: 10.1109/EuroSP.2018.00032

Google Scholar ePrint

[BHK⁺19]

Daniel J. Bernstein, Andreas Hülsing, Stefan Kölbl, Ruben Niederhagen, Joost Rijneveld, and Peter Schwabe. The SPHINCS+ Signature Framework. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 2129–2146, New York, NY, USA. 2019. Association for Computing Machinery. DOI: 10.1145/3319535.3363229

Google Scholar ePrint

[CC24]

Keng-Yu Chen and Jiun-Peng Chen. Masking Floating-Point Number Multiplication and Addition of Falcon: First- and Higher-order Implementations and Evaluations. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(2):276–303, Mar. 2024. DOI: 10.46586/tches.v2024.i2.276-303

Google Scholar ePrint

[CCJ⁺16]

Lily Chen, Lily Chen, Stephen Jordan, Yi-Kai Liu, Dustin Moody, Rene Peralta, and Daniel Perlner Ray A and Smith-Tone. Report on post-quantum cryptography, volume 12. US Department of Commerce, National Institute of Standards and Technology … 2016.

Google Scholar ePrint

[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 Gregor Leander, editor, Fast Software Encryption – FSE 2015, volume 9054 of Lecture Notes in Computer Science, pages 130–149, Istanbul, Turkey. March 8–11, 2015. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-662-48116-5_7

Google Scholar ePrint

[CS20]

Gaetan Cassiers and Francois-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

Google Scholar ePrint

[DKL⁺18]

Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, Peter Schwabe, Gregor Seiler, and Damien Stehlé. CRYSTALS-Dilithium: A Lattice-Based Digital Signature Scheme. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(1):238–268, Feb. 2018. DOI: 10.13154/tches.v2018.i1.238-268

Google Scholar ePrint

[EFG⁺22]

Thomas Espitau, Pierre-Alain Fouque, François Gérard, Mélissa Rossi, Akira Takahashi, Mehdi Tibouchi, Alexandre Wallet, and Yang Yu. Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon. In Orr Dunkelman and Stefan Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022, Part III, volume 13277 of Lecture Notes in Computer Science, pages 222–253, Trondheim, Norway. May 30 – June 3, 2022. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-07082-2_9

Google Scholar ePrint

[EFGT17]

Thomas Espitau, Pierre-Alain Fouque, Benoît Gérard, and Mehdi Tibouchi. Side-Channel Attacks on BLISS Lattice-Based Signatures: Exploiting Branch Tracing against strongSwan and Electromagnetic Emanations in Microcontrollers. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1857–1874, New York, NY, USA. 2017. Association for Computing Machinery. DOI: 10.1145/3133956.3134028

Google Scholar ePrint

[GBHLY16]

Leon Groot Bruinderink, Andreas Hülsing, Tanja Lange, and Yuval Yarom. Flush, Gauss, and Reload – A Cache Attack on the BLISS Lattice-Based Signature Scheme, pages 323–345. Springer Berlin Heidelberg 2016. DOI: 10.1007/978-3-662-53140-2_16

Google Scholar ePrint

[GMRR22]

Morgane Guerreau, Ange Martinelli, Thomas Ricosset, and Mélissa Rossi. The Hidden Parallelepiped Is Back Again: Power Analysis Attacks on Falcon. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2022(3):141–164, Jun. 2022. DOI: 10.46586/tches.v2022.i3.141-164

Google Scholar ePrint

[HPRR20]

James Howe, Thomas Prest, Thomas Ricosset, and Mélissa Rossi. Isochronous Gaussian Sampling: From Inception to Implementation. In Jintai Ding and Jean-Pierre Tillich, editors, Post-Quantum Cryptography - 11th International Conference, PQCrypto 2020, pages 53–71, Paris, France. April 15–17, 2020. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-44223-1_4

Google Scholar ePrint

[IEE19]

IEEE. IEEE Standard for Floating-Point Arithmetic. IEEE Std 754-2019 (Revision of IEEE 754-2008), 2019. DOI: 10.1109/IEEESTD.2019.8766229

Google Scholar ePrint

[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, Santa Barbara, CA, USA. August 17–21, 2003. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/978-3-540-45146-4_27

Google Scholar ePrint

[KA21]

Emre Karabulut and Aydin Aysu. FALCON Down: Breaking FALCON Post-Quantum Signature Scheme through Side-Channel Attacks. In 2021 58th ACM/IEEE Design Automation Conference (DAC), pages 691-696. December 2021. DOI: 10.1109/DAC18074.2021.9586131

Google Scholar ePrint

[KA24]

Emre Karabulut and Aydin Aysu. Masking FALCON’s Floating-Point Multiplication in Hardware. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2024(4):483–508, September 2024. DOI: 10.46586/tches.v2024.i4.483-508

Google Scholar ePrint

[Koc96]

Paul C. Kocher. Timing Attacks on Implementations of Diffie-Hellman, RSA, DSS, and Other Systems. In Neal Koblitz, editor, Advances in Cryptology – CRYPTO'96, volume 1109 of Lecture Notes in Computer Science, pages 104–113, Santa Barbara, CA, USA. August 18–22, 1996. Springer, Berlin, Heidelberg, Germany. DOI: 10.1007/3-540-68697-5_9

Google Scholar ePrint

[MHS⁺19]

Sarah McCarthy, James Howe, Neil Smyth, Séamus Brannigan, and Máire O’Neill. BEARZ Attack FALCON: Implementation Attacks with Countermeasures on the FALCON Signature Scheme. In Proceedings of the 16th International Joint Conference on e-Business and Telecommunications, pages 61–71. 2019. SCITEPRESS - Science and Technology Publications. DOI: 10.5220/0007834800610071

Google Scholar ePrint

[MOP08]

Stefan Mangard, Elisabeth Oswald, and Thomas Popp. Power analysis attacks: Revealing the secrets of smart cards, volume 31. Springer Science & Business Media 2008.

Google Scholar ePrint

[NIS24a]

NIST. Module-Lattice-Based Digital Signature Standard. NIST FIPS, 2024. DOI: 10.6028/NIST.FIPS.204.ipd

Google Scholar ePrint

[NIS24b]

NIST. Module-Lattice-Based Key-Encapsulation Mechanism Standard. NIST FIPS, 2024. DOI: 10.6028/NIST.FIPS.203.ipd

Google Scholar ePrint

[NIS24c]

NIST. Stateless Hash-Based Digital Signature Standard. NIST FIPS, 2024. DOI: 10.6028/NIST.FIPS.205.ipd

Google Scholar ePrint

[PBY17]

Peter Pessl, Leon Groot Bruinderink, and Yuval Yarom. To BLISS-B or not to be: Attacking strongSwan's Implementation of Post-Quantum Signatures. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1843–1855, New York, NY, USA. 2017. Association for Computing Machinery. DOI: 10.1145/3133956.3134023

Google Scholar ePrint

[PFH⁺20]

Thomas Prest, Pierre-Alain Fouque, Jeffrey Hoffstein, Paul Kirchner, Vadim Lyubashevsky, Thomas Pornin, Thomas Ricosset, Gregor Seiler, William Whyte, and Zhenfei Zhang. FALCON. 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.

Google Scholar ePrint

[RCDB24]

Prasanna Ravi, Anupam Chattopadhyay, Jan Pieter D’Anvers, and Anubhab Baksi. Side-channel and Fault-injection attacks over Lattice-based Post-quantum Schemes (Kyber, Dilithium): Survey and New Results. ACM Trans. Embed. Comput. Syst., 23(2), March 2024. DOI: 10.1145/3603170

Google Scholar ePrint

[Sho99]

Peter W. Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Review, 41(2):303-332, 1999. DOI: 10.1137/S0036144598347011

Google Scholar ePrint

[SPOG19]

Tobias Schneider, Clara Paglialonga, Tobias Oder, and Tim Güneysu. Efficiently Masking Binomial Sampling at Arbitrary Orders for Lattice-Based Crypto. In Dongdai Lin and Kazue Sako, editors, PKC 2019: 22nd International Conference on Theory and Practice of Public Key Cryptography, Part II, volume 11443 of Lecture Notes in Computer Science, pages 534–564, Beijing, China. April 14–17, 2019. Springer, Cham, Switzerland. DOI: 10.1007/978-3-030-17259-6_18

Google Scholar ePrint

[ZLYW23]

Shiduo Zhang, Xiuhan Lin, Yang Yu, and Weijia Wang. Improved Power Analysis Attacks on Falcon. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology – EUROCRYPT 2023, Part IV, volume 14007 of Lecture Notes in Computer Science, pages 565–595, Lyon, France. April 23–27, 2023. Springer, Cham, Switzerland. DOI: 10.1007/978-3-031-30634-1_19

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ay73zl7s

History

Submitted: 2024-09-12
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

Pierre-Augustin Berthet, Justine Paillet, Cédric Tavernier, Lilian Bossuet, and Brice Colombier, Masked Computation of the Floor Function and Its Application to the FALCON Signature. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/ay73zl7s.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-4-9,
    author = "Berthet, Pierre-Augustin and Paillet, Justine and Tavernier, Cédric and Bossuet, Lilian and Colombier, Brice",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Masked Computation of the Floor Function and Its Application to the {FALCON} Signature",
    volume = "1",
    number = "4",
    date = "2025-01-13",
    year = "2025",
    issn = "3006-5496",
    doi = "10.62056/ay73zl7s"
}

TY - JOUR
AU - Berthet, Pierre-Augustin
AU - Paillet, Justine
AU - Tavernier, Cédric
AU - Bossuet, Lilian
AU - Colombier, Brice
PY  - 2025
TI  - Masked Computation of the Floor Function and Its Application to the FALCON Signature
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 4
DO  - 10.62056/ay73zl7s
UR  - https://doi.org/10.62056/ay73zl7s
AB  - <p>     FALCON is a signature selected for standardisation of the new Post-Quantum Cryptography (PQC) primitives by the National Institute of Standards and Technology (NIST). However, it remains a challenge to define efficient countermeasures against side-channel attacks (SCA) for this algorithm. FALCON is a lattice-based signature that relies on rational numbers, which is unusual in the cryptography field. Although recent work proposed a solution to mask the addition and the multiplication, some roadblocks remain, most noticeably, how to protect the floor function. In this work, we propose to complete the first existing tests of hardening FALCON against SCA. We perform the mathematical proofs of our methods as well as formal security proofs in the probing model by ensuring Multiple Input Multiple Output Strong Non-Interference (MIMO-SNI) security. We provide performances on a laptop computer of our gadgets as well as of a complete masked FALCON. We notice significant overhead in doing so and discuss the deployability of our method in a real-world context. </p>
ER  -

Pierre-Augustin Berthet, Justine Paillet, Cédric Tavernier, Lilian Bossuet, and Brice Colombier, Masked Computation of the Floor Function and Its Application to the FALCON Signature. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/ay73zl7s.