FrodoKEM: key encapsulation from unstructured lattices

Short answer: FrodoKEM is a family of key-encapsulation mechanisms (KEMs) whose designers say they are conservative yet practical post-quantum constructions. Its security derives from cautious parameterizations of the learning with errors (LWE) problem on generic, algebraically unstructured lattices. The designers propose it as an alternative to more efficient schemes built on structured lattices, such as ML-KEM. All performance and security statements here are the designers' own.

The idea: unstructured lattices

The FrodoKEM website says it is a family of KEMs designed to be conservative yet practical post-quantum constructions, whose security derives from cautious parameterizations of the well-studied learning with errors problem. It says LWE in turn has close connections to conjectured-hard problems on generic, algebraically unstructured lattices.

A 2025 paper on the IACR ePrint archive describing FrodoKEM says it is proposed as an alternative to the more efficient lattice schemes that use algebraically structured lattices, such as the recently standardized ML-KEM. It argues that, by relying on generic lattices, FrodoKEM minimizes the potential for future attacks that exploit algebraic structure, while enabling simple and compact implementations. We cover the structured-lattice scheme in our article on ML-KEM.

How the scheme is built

A September 2025 FrodoKEM proposal document says the core building block is a public-key encryption scheme called FrodoPKE, whose IND-CPA security is tightly related to the hardness of a corresponding learning with errors problem. As a key encapsulation mechanism, FrodoKEM is a two-pass protocol that allows two parties to derive a shared secret, which can then be used to establish a secure channel with a symmetric-key algorithm such as AES.

The ePrint paper says FrodoKEM obtains single-target IND-CCA security using a variant of the Fujisaki-Okamoto transform applied to FrodoPKE. It adds that, using a new tool called the Salted Fujisaki-Okamoto transform, FrodoKEM is also shown to tightly achieve multi-target security, without increasing the FrodoPKE message length and with a negligible performance impact.

Variants

The proposal document says the matrix A is generated with a pseudorandom generator, with two main variants using either AES128 or SHAKE128. It also describes a standard variant that places no restriction on key pair reuse, suitable for applications where many ciphertexts may be encrypted to one public key, and an ephemeral variant, eFrodoKEM, suitable where the number of ciphertexts per public key is fairly small. The website says the ephemeral variant requires a fresh key pair after a fairly small number of protocol executions, for example 2 to the power 8. The document specifies parameter sets targeting three security levels, and says the 640 sets match or exceed the brute-force security of AES128.

What the authors report about speed

The ePrint paper says its plain C implementations demonstrate that FrodoKEM remains practical despite its conservative design. For example, it reports that 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. These are the authors' own measurements on their own implementations, and results on other platforms will differ.

What this does not tell you

This article summarises the designers' website, proposal document and paper, so none of it is independent evaluation. It does not compare FrodoKEM with ML-KEM on key and ciphertext sizes, and it makes no claim about deployment. A conservative security argument is not the same as a standard.

FAQ

What is FrodoKEM?

A family of conservative post-quantum key-encapsulation mechanisms based on learning with errors over generic, unstructured lattices, per its designers.

How does it differ from ML-KEM?

The ePrint paper says ML-KEM uses algebraically structured lattices and is more efficient, while FrodoKEM relies on generic lattices to reduce exposure to attacks that exploit structure.

What are the two variants?

Standard, with no restriction on key pair reuse, and ephemeral (eFrodoKEM), for few ciphertexts per public key.

Is it fast enough?

The authors report about 0.97 ms on a server-class processor and 4.98 ms on a smartphone-class processor at security level 1, on their implementations.

Is it a standard?

These sources describe it as a proposal. They do not state that it is standardized.