FrodoKEM: The Conservative Rock in the Storm of Post-Quantum Cryptography

Introduction

Post-quantum cryptography operates under an immense efficiency imperative. Keys must be small, computations fast, protocols lean. Algorithms that fail to meet these requirements had little chance in NIST's standardisation competition – and so ML-KEM (Kyber) emerged as the primary standard for quantum-safe key encapsulation: compact, fast, elegant.

But there is one algorithm that deliberately resists this efficiency imperative. Not out of indifference, but out of conviction. FrodoKEM is the answer to a question that is easily lost in the enthusiasm surrounding structured lattice schemes: What if we are wrong?

What if the algebraic structure that makes ML-KEM so efficient one day becomes its weakness? What if a cryptanalytic breakthrough shakes the security assumptions of Ring-LWE or Module-LWE – just as Shor once shook RSA and ECC?

FrodoKEM gives a clear answer to this question: it completely foregoes algebraic structure, accepts larger keys and slower computations in return – and buys itself a level of security confidence grounded in one of the most thoroughly studied problems in lattice cryptography. It is not a compromise. It is a philosophy.

The Foundation: Plain LWE Instead of Ring-LWE

To understand why FrodoKEM is so conservative, one must understand what ML-KEM builds its efficiency upon – and what FrodoKEM deliberately does differently.

ML-KEM is based on Module-LWE, a structured variant of the Learning with Errors problem. It uses polynomials in a quotient ring $\mathbb{Z}_q[x]/(x^n + 1)$. This ring structure allows matrix multiplications to be replaced by fast polynomial multiplication – accelerated by the Number-Theoretic Transform (NTT). The result is very small keys and very fast operations.

FrodoKEM, by contrast, is based on plain LWE – the original, unstructured Learning with Errors problem introduced by Oded Regev in 2005. There is no ring, no polynomials, no algebraic shortcuts. Instead, FrodoKEM works with genuine random matrices over $\mathbb{Z}_q$.

The LWE problem can be described as follows: given a random matrix $\mathbf{A} \in \mathbb{Z}_q^{m \times n}$, a secret vector $\mathbf{s} \in \mathbb{Z}_q^n$, and a small error vector $\mathbf{e}$, it is computationally hard to reconstruct $\mathbf{s}$ from $\mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e}$. The noise – that is, $\mathbf{e}$ – is not a disturbance but a mathematical necessity: without it, the system would be trivially solvable.

The critical difference from Ring-LWE lies in the matrix $\mathbf{A}$. In structured schemes, $\mathbf{A}$ is not truly random – it has a cyclic or negacyclic structure generated from a single polynomial. This is efficient, but it means security depends on this structure offering no attack surface. In FrodoKEM, $\mathbf{A}$ is a genuine random matrix with no algebraic properties whatsoever. The security reduction to the general LWE problem is therefore more direct and requires no additional structural assumptions.

Key Generation: How FrodoKEM Builds a Key Pair

Key generation in FrodoKEM follows an elegant but computationally demanding logic.

Step 1: Matrix generation. A large matrix $\mathbf{A} \in \mathbb{Z}_q^{n \times n}$ is generated pseudorandomly from a public seed. FrodoKEM supports two primitives here: AES-128 (in ECB mode, ideal for hardware with AES-NI acceleration) or SHAKE-128 (a Keccak-based XOF, faster on software without AES-NI). The seed itself is public – the security of the system does not depend on keeping $\mathbf{A}$ secret.

Step 2: Error sampling. The private key consists of two matrices with small entries: $\mathbf{S}$ and $\mathbf{E}$, both sampled from a discrete Gaussian distribution. These error matrices are the heart of the security – their entries are small (typically single digits), but their presence makes the system computationally hard to attack.

Step 3: Public key. The public key is $\mathbf{B} = \mathbf{A}\mathbf{S} + \mathbf{E} \pmod{q}$. Anyone who knows $\mathbf{B}$ and $\mathbf{A}$ but not $\mathbf{S}$ and $\mathbf{E}$ cannot reconstruct $\mathbf{S}$ – that is exactly the LWE problem.

The decisive cost lies in the matrix multiplication $\mathbf{A}\mathbf{S}$. In ML-KEM, the NTT reduces this to $\mathcal{O}(n \log n)$. In FrodoKEM with a genuine $n \times n$ matrix, the naive approach is $\mathcal{O}(n^3)$ – optimised in practice, but still considerably more expensive. This is the direct price of the absence of algebraic structure.

Encapsulation and Decapsulation

The actual key encapsulation – that is, negotiating a shared secret – works in FrodoKEM according to the principle of the Regev cryptosystem, adapted for KEMs.

Encapsulation (sender): The sender generates additional error matrices $\mathbf{S}'$, $\mathbf{E}'$ and $\mathbf{E}''$, computes $\mathbf{B}' = \mathbf{S}'\mathbf{A} + \mathbf{E}'$ and $\mathbf{C} = \mathbf{S}'\mathbf{B} + \mathbf{E}'' + \text{encode}(\mu)$, where $\mu$ is the message to be encapsulated (the key material seed). The ciphertext is the tuple $(\mathbf{B}', \mathbf{C})$.

Decapsulation (receiver): The receiver computes $\mathbf{M} = \mathbf{C} - \mathbf{S}^T\mathbf{B}'$. Due to the LWE structure, the random terms almost cancel out – leaving $\text{encode}(\mu)$ plus a small error term. Since the error is small, $\mu$ can be recovered by rounding. The shared key is then derived from $\mu$ via a hash function.

Rounding is the critical step: it works precisely when the accumulated error remains small enough – which is guaranteed by the careful choice of error distribution and parameters.

Two Variants: FrodoKEM and eFrodoKEM

FrodoKEM exists in two variants addressing different deployment scenarios.

eFrodoKEM (Ephemeral) is optimised for scenarios where a fresh key pair is generated for each session. The public key is used once and then discarded. This is the classic scenario in the TLS handshake: forward secrecy is built in, because there is no long-lived private key that could be compromised.

FrodoKEM (Salted) addresses a more subtle problem: multi-ciphertext attacks. When a long-lived public key is reused for many encapsulations, an attacker collecting many ciphertexts may potentially accumulate information. FrodoKEM-Salted addresses this by incorporating a public salt value into the key generation process, making each encapsulation unique – without altering the security structure.

The choice between the two variants is therefore not a matter of preference but of deployment scenario: short-lived keys in ephemeral protocols use eFrodoKEM. Long-lived public keys in infrastructures experiencing many encapsulations per key pair use FrodoKEM-Salted.

Parameters: Three Security Levels, Two Primitives

FrodoKEM comes in three parameter sets corresponding to NIST Security Categories 1, 3 and 5:

Variant	NIST Level	Equivalent
FrodoKEM-640	1	AES-128
FrodoKEM-976	3	AES-192
FrodoKEM-1344	5	AES-256

Each parameter set is also available in two primitive variants: AES and SHAKE. AES-NI-capable hardware – meaning virtually every modern server processor and most smartphones – significantly accelerates the AES variant. Without hardware acceleration, SHAKE is typically the faster choice. Both variants are security-equivalent; the choice is purely an implementation decision.

Why the BSI Thinks Differently from NIST

The fact that NIST chose ML-KEM as its primary standard and not FrodoKEM is not a rejection of FrodoKEM. It is a prioritisation decision in favour of efficiency and broad deployability.

The BSI has weighed this differently. In its technical guidelines, the BSI explicitly recommends FrodoKEM at Levels 3 and 5 for applications with long-term confidentiality requirements – precisely the scenarios most vulnerable to Store Now, Decrypt Later attacks. Anyone protecting data that must remain secret in ten or twenty years is on the safe side with FrodoKEM.

This is also the context in which Classic McEliece and FrodoKEM are frequently mentioned together: both are BSI favourites for conservative, long-term security. Classic McEliece is based on code-based cryptography and is even more conservative than FrodoKEM – with even larger keys, but in return a nearly fifty-year security history for the underlying Goppa codes. FrodoKEM and Classic McEliece are therefore not competitors to ML-KEM, but complements – for contexts where efficiency yields to maximum security confidence.

The fact that the French ANSSI and the Dutch authorities NLNCSA and AIVD recommend FrodoKEM alongside the BSI is no coincidence. It is a coordinated signal from European security agencies: we trust structured lattices – but we want a fallback option that makes no algebraic assumptions.

Implementation: Simplicity as a Security Feature

One frequently overlooked advantage of FrodoKEM is its implementation friendliness. Structured lattice schemes like ML-KEM require a correct NTT implementation, careful handling of polynomial rings and complex modularity properties. Errors in these areas can lead to side-channel attacks – timing attacks, power analyses, cache timing.

FrodoKEM works exclusively with matrix multiplications and straightforward error sampling over integer vectors. The operations are direct, well-parallelisable and naturally easier to implement in constant time. In security-critical implementations, this is not a luxury but a fundamental requirement: algorithms that run in variable time leak information about secret values.

The fact that FrodoKEM naturally lends itself to constant-time implementation is therefore not merely an academic detail. It is a practical advantage in the real world of embedded systems, HSMs and smartcards, where side-channel resistance cannot be retrofitted but must be designed into the algorithm from the outset.

Conclusion: The Insurance Policy of the Post-Quantum World

FrodoKEM is not the fastest algorithm. It is not the most compact. And it is not the one most developers will integrate into their applications first.

But it is the algorithm that European security agencies trust when it matters. The one that takes no algebraic shortcuts. The one that will still be standing in the event of a cryptanalytic breakthrough against structured lattices.

In a world where crypto-agility is becoming mandatory and migration decisions are being made for the next twenty years, FrodoKEM is the answer to a simple question: what if we are wrong?

The answer is: then we have FrodoKEM.