Paper 2023/158

Enabling FrodoKEM on Embedded Devices

Joppe W. Bos, NXP (Belgium)
Olivier Bronchain, NXP (Belgium)
Frank Custers, NXP (Netherlands)
Joost Renes, NXP (Netherlands)
Denise Verbakel, Radboud University Nijmegen
Christine van Vredendaal

FrodoKEM is a lattice-based Key Encapsulation Mechanism (KEM) based on unstructured lattices. From a security point of view this makes it a conservative option to achieve post-quantum security, hence why it is favored by several European authorities (e.g., German BSI and French ANSSI). Relying on unstructured instead of structured lattices (e.g., CRYSTALS-Kyber) comes at the cost of additional memory usage, which is particularly critical for embedded security applications such as smart cards. For example, prior FrodoKEM-640 implementations (using AES) on Cortex-M4 require more than 80 kB of stack making it impossible to run on some embedded systems. In this work, we explore several stack reduction strategies and the resulting time versus memory trade-offs. Concretely, we reduce the stack consumption of FrodoKEM by a factor 2–3× compared to the smallest known implementations with almost no impact on performance. We also present various time-memory trade-offs going as low as 8 kB for all AES parameter sets, and below 4 kB for FrodoKEM-640. By introducing a minor tweak to the FrodoKEM specifications, we additionally reduce the stack consumption down to 8 kB for all the SHAKE versions. As a result, this work enables FrodoKEM on more resource constrained embedded systems.

Available format(s)
Publication info
A minor revision of an IACR publication in TCHES 2023
Post-Quantum CryptographySmall-stackFrodoKEM
Contact author(s)
joppe bos @ nxp com
olivier bronchain @ nxp com
frank custers_1 @ nxp com
joost renes @ nxp com
denise verbakel @ ru nl
christine cloostermans @ nxp com
2023-04-14: revised
2023-02-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Joppe W. Bos and Olivier Bronchain and Frank Custers and Joost Renes and Denise Verbakel and Christine van Vredendaal},
      title = {Enabling FrodoKEM on Embedded Devices},
      howpublished = {Cryptology ePrint Archive, Paper 2023/158},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.