Douglas Stebila

FrodoKEM: A CCA-secure learning with errors key encapsulation mechanism

Abstract

Large-scale quantum computers capable of implementing Shor's algorithm pose a significant threat to the security of the most widely used public-key cryptographic schemes. This risk has motivated substantial efforts by standards bodies and government agencies to identify and standardize quantum-safe cryptographic systems. Among the proposed solutions, lattice-based cryptography has emerged as the foundation for some of the most promising protocols.

This paper describes FrodoKEM, a family of conservative key-encapsulation mechanisms (KEMs) whose security is based on generic, “unstructured” lattices. FrodoKEM is proposed as an alternative to the more efficient lattice schemes that utilize algebraically structured lattices, such as the recently standardized ML-KEM scheme. By relying on generic lattices, FrodoKEM minimizes the potential for future attacks that exploit algebraic structures while enabling simple and compact implementations. Our plain C implementations demonstrate that, despite its conservative design and parameterization, FrodoKEM remains practical. For instance, the full protocol at NIST security level 1 runs in approximately 0.97 ms on a server-class processor, and 4.98 ms on a smartphone-class processor.

FrodoKEM obtains (single-target) IND-CCA security using a variant of the Fujisaki-Okamoto transform, applied to an underlying public-key encryption scheme called FrodoPKE. In addition, using a new tool called the Salted Fujisaki-Okamoto (SFO) transform, FrodoKEM is also shown to tightly achieve multi-target security, without increasing the FrodoPKE message length and with a negligible performance impact, based on the multi-target IND-CPA security of FrodoPKE.

Keywords: post-quantum cryptography, key encapsulation mechanism, lattice-based cryptography, learning with errors, Fujisaki-Okamoto transform, multi-target security

Reference

Lewis Glabush, Patrick Longa, Michael Naehrig, Chris Peikert, Douglas Stebila, Fernando Virdia. FrodoKEM: A CCA-secure learning with errors key encapsulation mechanism. IACR Communications in Cryptology, 2(3):25. October 2025. © The authors.

Download

Code

• FrodoKEM reference implementation: GitHub

BibTeX

@article{CIC:GLNPSV25,
 	Author = {Lewis Glabush and Patrick Longa and Michael Naehrig and Chris Peikert and Douglas Stebila and Fernando Virdia},
 	Doi = {10.62056/ayivom2hd},
 	Journal = {IACR Communications in Cryptology},
 	Month = oct,
 	Number = {3},
 	Pages = {25},
 	Title = {{FrodoKEM}: A {CCA}-secure learning with errors key encapsulation mechanism},
 	Volume = {2},
 	Year = {2025}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2022-03187
• NSERC Alliance grant ALLRP 578463-22
• UKRI grant EP/Y02432X/1