Paper 2025/1308

Efficient High-Order Masking of FrodoKEM’s CDT-Based Gaussian Sampler

Aurélien Greuet, IDEMIA Secure Transactions, Cryptography & Security Labs

Nathan Reboud, IDEMIA Secure Transactions, Cryptography & Security Labs

Rina Zeitoun, IDEMIA Secure Transactions, Cryptography & Security Labs

Abstract

FrodoKEM is a conservative lattice-based KEM based on the Learning With Errors problem. While it was not selected for NIST standardization, it remains a strong candidate for high-security applications and is recommended by several national agencies, including BSI, ANSSI, and the EUCC. Its reliance on CDT-based Gaussian sampling presents a significant challenge for side-channel secure implementations. While recent work by Gérard and Guerreau [GG25] has shown that masking FrodoKEM is feasible, the Gaussian sampler remains a major bottleneck, accounting for between 34% and 65% of the execution time. In this work, we introduce a new high-order masking gadget for CDT sampling, provably secure in the ISW probing model and significantly more efficient than previous approaches. We instantiate and evaluate our design on a real-world setup to assess its side-channel resistance in the context of FrodoKEM, using a complete first-order masked implementation on Cortex-M3, which reflects the most relevant practical threat model. Compared with [GG25] at first order, the cost of the sampler is reduced by at least 82% and the number of random generations by at least 69%. Higher-order security is also fully supported through a generic C implementation, with some selected gadgets hand-optimized in assembly to improve efficiency.

@misc{cryptoeprint:2025/1308,
      author = {Elie Eid and Aurélien Greuet and Nathan Reboud and Rina Zeitoun},
      title = {Efficient High-Order Masking of {FrodoKEM}’s {CDT}-Based Gaussian Sampler},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1308},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1308}
}