Improving the Masked Division for the FALCON Signature

Pierre-Augustin Berthet; Cédric Tavernier; Justine Paillet; Yousuf Alsalami; Majid Khonji; Chan Yeun; Hani Saleh; Muna A. Alshehhi; Ahmed S. Al Ali

Paper 2025/628

Improving the Masked Division for the FALCON Signature

Pierre-Augustin Berthet

, Laboratoire Traitement et Communication de l’Information, Hensoldt France SAS

Cédric Tavernier

, Hensoldt France SAS

Justine Paillet

, Hensoldt France

Yousuf Alsalami

, Khalifa university

Majid Khonji

, Khalifa university

Chan Yeun

, Khalifa university

Hani Saleh

, Khalifa university

Muna A. Alshehhi

, Khalifa university

Ahmed S. Al Ali, Khalifa university

Abstract

FALCON is a post-quantum signature selected by the National Institute of Standards and Technology (NIST). Although its side-channel resilience has been studied and a masking countermeasure proposed, the division is a major performance bottleneck. This work proposes a different approach to the masked FALCON division. We use the Newton-Raphson method and a convergent sequence to approximate this operation. The first term of the sequence is evaluated using pre-calculated second-order minimax polynomials. As a consequence, computing the inverse only requires 5 masked additions and 8 masked multiplications, compared to the roughly 55 masked additions required by the previous state-of-the-art. Formal security proofs using the MIMO-SNI criteria are also provided.

Note: Minimax polynomials are now second-order, which saves one iteration in the sequence (3 operations) at the cost of 2 extra operations in the minimax polynomial. Formal proofs were adjusted accordingly.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint.
Keywords: Post-Quantum Cryptography FALCON Side-Channel Analysis Masking MIMO-SNI
Contact author(s): pierre augustin berthet @ gmail com
tavernier cedric @ gmail com
paillet justine @ gmail com
yousuf alsalami @ ku ac ae
majid khonji @ ku ac ae
chan yeun @ ku ac ae
hani saleh @ ku ac ae
100035578 @ ku ac ae
100059224 @ ku ac ae
History: 2026-07-16: last of 2 revisions; 2025-04-07: received; See all versions
Short URL: https://ia.cr/2025/628
License: CC BY

BibTeX

@misc{cryptoeprint:2025/628,
      author = {Pierre-Augustin Berthet and Cédric Tavernier and Justine Paillet and Yousuf Alsalami and Majid Khonji and Chan Yeun and Hani Saleh and Muna A. Alshehhi and Ahmed S. Al Ali},
      title = {Improving the Masked Division for the {FALCON} Signature},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/628},
      year = {2025},
      url = {https://eprint.iacr.org/2025/628}
}