up:: The New Standards MOC

FrodoKEM

FrodoKEM is a post-quantum key encapsulation mechanism built on plain Learning With Errors over generic, unstructured lattices, with none of the ring or module structure that the efficient lattice schemes use. That choice is its whole identity. By resting on the most conservative lattice assumption available, FrodoKEM trades away the small keys and speed of a scheme like ML-KEM in exchange for a security argument that does not depend on any extra algebraic structure. NIST declined to standardize it precisely because it is slow and its keys are large, yet Germany’s BSI and France’s ANSSI both keep FrodoKEM on their recommended lists as the conservative hedge for entities that want a larger margin against a future break of structured-lattice cryptanalysis.

Source: FrodoKEM team, “FrodoKEM: Practical Quantum-Secure Key Encapsulation from Generic Lattices,” project overview, frodokem.org.

The short version:

• FrodoKEM is a lattice-based KEM built on plain LWE over generic, algebraically unstructured lattices, the most conservative lattice assumption in use.
• Its security derives, in the team’s own words, from “cautious parameterizations of the well-studied learning with errors problem, which in turn has close connections to conjectured-hard problems on generic, algebraically unstructured lattices.”
• The tradeoff is size and speed: FrodoKEM public keys and ciphertexts run to tens of kilobytes, roughly ten times larger than ML-KEM, because dropping the ring structure removes the compression that structure enables.
• NIST did not standardize it. ML-KEM won the KEM slot on efficiency, and FrodoKEM is not on the NIST FIPS track.
• BSI and ANSSI keep it on their recommended lists as the unstructured-lattice conservative option, the hedge against a structured-lattice break, and BSI names FrodoKEM-976 and FrodoKEM-1344 specifically.
• It resists Shor’s algorithm for the same reason every lattice scheme does, because its hardness is geometric rather than number-theoretic.

Picture two ways to build a safe. One is milled from a single block of steel with an elegant internal mechanism, compact and quick to open with the right key. The other is a plain, oversized steel box with a straightforward lock and thick walls, heavier and slower to move but with almost nothing clever inside for a thief to reverse-engineer. FrodoKEM is the plain heavy box. It gives up the elegance that makes structured-lattice schemes fast and small, and in return it offers a security story with fewer moving parts to study.

What is FrodoKEM?

FrodoKEM is a key encapsulation mechanism in the lattice family whose defining feature is that it uses the plain, unstructured form of Learning With Errors rather than a ring or module variant. Its job is key establishment: two parties agree on a shared secret, which they feed into ordinary symmetric encryption, without a quantum computer being able to recover that secret from what crosses the wire.

Three facts pin down its identity:

1. Plain LWE, no ring or module. The efficient lattice schemes, including ML-KEM, work over structured algebraic objects (rings and modules) to shrink their keys. FrodoKEM stays in plain LWE, where the secret is recovered from noisy linear equations over a generic lattice with no exploitable algebraic structure. The name is a nod to the “Frodo” line of research on generic-lattice key exchange.
2. Conservative by design. The FrodoKEM specification frames the scheme’s security around “cautious parameterizations of the well-studied learning with errors problem,” tied to “conjectured-hard problems on generic, algebraically unstructured lattices.” The point is not performance; it is resting on the smallest, most-studied set of assumptions.
3. IND-CCA security at three levels. FrodoKEM offers IND-CCA-secure key encapsulation at three parameter sets targeting NIST security levels 1, 3, and 5.

Source: FrodoKEM team, frodokem.org (plain LWE over generic unstructured lattices; IND-CCA at three levels; “cautious parameterizations of the well-studied learning with errors problem”).

Why does FrodoKEM avoid ring and module structure?

FrodoKEM avoids structure because structure is both the source of a lattice scheme’s efficiency and the largest unknown in its long-term security. The reasoning tracks the same instinct behind NTRU Prime, taken one step further. Where NTRU Prime keeps a ring but strips out its symmetry, FrodoKEM drops the ring entirely and works over plain LWE.

The tension it resolves:

1. Structured lattices are fast but carry extra assumptions. ML-KEM gets its small keys and speed from working over a module of polynomial rings. That structure is what makes the scheme practical, and it is also an additional mathematical object a cryptanalyst can study. No efficient attack exploits it today, but the possibility is the reason cryptographers watch structured lattices closely.
2. Plain LWE has the longest, plainest track record. The generic Learning With Errors problem is one of the most heavily studied assumptions in lattice cryptography, and it comes with worst-case-to-average-case hardness connections that the structured variants only approximate. FrodoKEM’s argument is that a KEM resting on that assumption alone is the most defensible choice for the highest-assurance work.
3. The cost is paid in bytes, not security. Removing the structure removes the compression it enabled, so FrodoKEM’s keys and ciphertexts grow by roughly an order of magnitude. That is a deployment cost, not a cryptographic weakness, and it is the specific reason NIST chose the more efficient ML-KEM instead.

So FrodoKEM occupies the conservative end of the lattice spectrum. ML-KEM is the efficient default; NTRU Prime is a structure-reduced middle; FrodoKEM is the plain-LWE floor that gives up the most performance for the fewest assumptions.

Source: FrodoKEM team, frodokem.org (generic algebraically unstructured lattices as the conservative design basis).

What are FrodoKEM’s parameter sets and sizes?

FrodoKEM defines three parameter sets across NIST security levels 1, 3, and 5, and its sizes are what set it apart from the structured schemes. The AES variants (which use AES to generate the large public matrix) carry the byte counts below.

Parameter set	NIST level	Public key (bytes)	Ciphertext (bytes)	Shared secret (bytes)
FrodoKEM-640-AES	1	9,616	9,752	16
FrodoKEM-976-AES	3	15,632	15,792	24
FrodoKEM-1344-AES	5	21,520	21,696	32

Source: Open Quantum Safe project, liboqs KEM datasheet, “FrodoKEM,” reproducing the sizes from the FrodoKEM specification, openquantumsafe.org/liboqs/algorithms/kem/frodokem.html.

The contrast with ML-KEM is the whole story of where FrodoKEM fits. An ML-KEM-768 public key is about 1,184 bytes and its ciphertext about 1,088 bytes, so FrodoKEM-976 at level 3 carries a public key and ciphertext each roughly 14 to 15 times larger. That extra weight is the price of dropping the module structure, and it is why FrodoKEM is a poor fit for protocols that ship the public key on every handshake and a reasonable fit where the conservative assumption matters more than the byte count. FrodoKEM also offers “SHAKE” variants that generate the matrix with SHAKE instead of AES, with the same size profile.

Why do BSI and ANSSI recommend it if NIST didn’t standardize it?

Because the European conservative authorities weight the assumption differently than NIST weighted efficiency. NIST ran its selection heavily on performance, and FrodoKEM’s large keys and slow operations ruled it out against ML-KEM. BSI and ANSSI both accept ML-KEM as the efficient default, and both also keep FrodoKEM on their recommended lists as the conservative alternative for entities that want a larger safety margin against a future structured-lattice break.

1. BSI (Germany). TR-02102-1 keeps FrodoKEM on its recommended list of key-agreement mechanisms and names FrodoKEM-976 and FrodoKEM-1344 as the unstructured-lattice conservative choice. Where U.S. guidance leans on structured-lattice ML-KEM alone, BSI keeps FrodoKEM (unstructured lattice) and Classic McEliece (code-based) as recommended options for a larger margin against a structured-lattice cryptanalytic advance.
2. ANSSI (France). ANSSI endorses FrodoKEM as a conservative KEM alternative built on unstructured lattices, which rest on a more conservative security assumption than the structured lattices behind ML-KEM. It is offered for entities that want a larger margin, and, per ANSSI’s hybrid-first rule, whichever KEM is chosen is to be deployed inside a hybrid construction with a recognized classical key exchange through the transition window.

Sources: BSI, TR-02102-1 Version 2026-01, §2.4 (FrodoKEM among recommended key-agreement mechanisms; FrodoKEM-976 and FrodoKEM-1344 as the unstructured-lattice conservative option), PDF; ANSSI, “ANSSI views on the Post-Quantum Cryptography transition” (FrodoKEM as the unstructured-lattice conservative KEM alternative), cyber.gouv.fr.

The net picture is a scheme that lost the NIST efficiency contest but earned a durable place in conservative European guidance: NIST’s deployable default is ML-KEM, while FrodoKEM is the plain-LWE reserve that BSI and ANSSI still recommend for the highest-assurance, most-cautious deployments. Keeping an unstructured-lattice option in play is the same diversification instinct that put code-based Classic McEliece and HQC into the picture, applied inside the lattice world.

Is FrodoKEM quantum-safe?

Yes, as far as current research shows, and its conservative assumption is the reason it is often chosen for the highest-assurance work. FrodoKEM is a post-quantum design whose hardness is the difficulty of solving LWE over a generic lattice, a geometric problem rather than a number-theoretic one.

1. It resists Shor’s algorithm. Shor’s breaks RSA and elliptic-curve cryptography by exploiting periodic structure that a lattice problem does not have, so it gives an attacker no advantage against FrodoKEM.
2. Grover’s algorithm is only a bounded discount. Grover’s quadratic search speedup is a real but limited effect, and FrodoKEM’s parameters are chosen with it accounted for.
3. Plain LWE is the strongest hedge against future advances. Because FrodoKEM avoids the extra algebraic structure that structured-lattice cryptanalysis targets, an advance that broke a ring or module scheme would not automatically carry over to it, which is precisely why the conservative authorities keep it in reserve.

The honest framing is that FrodoKEM is not more quantum-safe than ML-KEM in any known sense today; both are believed secure against a quantum computer. FrodoKEM’s advantage is narrower and specific: it depends on fewer assumptions, so it is the better bet if the structured-lattice assumption is the thing that eventually cracks.

Source: FrodoKEM quantum-security basis (generic-lattice LWE), frodokem.org; lattice quantum-resistance rationale shared across the family, NIST FIPS 203, August 2024.

Common misconceptions

1. “FrodoKEM is a NIST standard.” It is not. NIST standardized ML-KEM for the KEM slot and declined FrodoKEM on efficiency grounds. FrodoKEM lives on in BSI and ANSSI guidance, not on the NIST FIPS track.
2. “FrodoKEM’s large keys mean it’s insecure.” The large keys are a deployment cost of dropping the ring structure, not a cryptographic weakness. The whole reason to accept them is a more conservative security assumption.
3. “FrodoKEM is more quantum-resistant than ML-KEM.” Both are believed secure against a quantum computer. FrodoKEM’s edge is that it rests on fewer assumptions, so it is a hedge specifically against a future break of structured lattices, not a general step up in quantum safety.
4. “BSI and ANSSI recommend FrodoKEM instead of ML-KEM.” They recommend ML-KEM as the efficient default and keep FrodoKEM alongside it as the conservative alternative. It is an additional option for cautious deployments, not a replacement for the main line.
5. “FrodoKEM and NTRU Prime are the same conservative idea.” Both reduce reliance on algebraic structure, but NTRU Prime keeps a prime-degree ring and strips its symmetry, while FrodoKEM drops the ring entirely and uses plain LWE, so FrodoKEM is the more conservative and the larger of the two.

Questions people ask

What is FrodoKEM in simple terms? It is a lattice-based key encapsulation mechanism built on the plain, unstructured form of Learning With Errors, with no ring or module shortcuts. That makes it slower and its keys much larger than ML-KEM, but it rests on a more conservative security assumption, which is why cautious authorities keep it in reserve.

Is FrodoKEM a NIST standard? No. NIST selected ML-KEM as the KEM standard and did not standardize FrodoKEM, largely because FrodoKEM’s keys and operations are much larger and slower. It remains recommended by BSI and ANSSI as a conservative option.

Why do BSI and ANSSI recommend FrodoKEM? Because it rests on unstructured lattices, a more conservative assumption than the structured lattices behind ML-KEM. Both agencies keep it on their recommended lists as the hedge for entities that want a larger margin against a future break of structured-lattice cryptanalysis, with BSI naming FrodoKEM-976 and FrodoKEM-1344 specifically.

How much larger are FrodoKEM’s keys than ML-KEM’s? Roughly an order of magnitude. FrodoKEM-976 at NIST level 3 uses a public key of about 15,632 bytes and a ciphertext of about 15,792 bytes, against roughly 1,184 and 1,088 bytes for ML-KEM-768. Dropping the module structure is what removes the compression.

Is FrodoKEM quantum-safe? Yes, as far as current research shows. Its hardness is generic-lattice LWE, which Shor’s algorithm does not solve, and Grover’s gives only a bounded search speedup the parameters already absorb. Its specific value is that it depends on fewer assumptions than the structured schemes.

Should my organization deploy FrodoKEM instead of ML-KEM? For general-purpose key establishment, no. ML-KEM is the finalized, efficient default and the right first move. FrodoKEM is the conservative reserve to consider when the deployment can absorb its large keys and the stronger assumption argument genuinely matters, or when a French or German conservative-guidance requirement calls for it.

How does FrodoKEM relate to NTRU Prime? Both reduce dependence on algebraic structure, but at different depths. NTRU Prime keeps a ring and removes its symmetry; FrodoKEM removes the ring entirely and uses plain LWE. FrodoKEM is the more conservative and the larger, and it is the one European conservative guidance names for the highest-assurance cases.

---

FrodoKEM is the scheme you reach for when the assumption matters more than the byte count, and when the most-studied, least-structured lattice problem is worth its weight in kilobytes. Everything here is the map, given freely. When your team needs to decide whether a conservative unstructured-lattice KEM belongs anywhere in your architecture alongside the efficient default, that’s what an alignment briefing is for.

Last verified 2026-07-12 · Maintained by Addie LaMarr, LaMarr Labs.