FrodoKEM

FrodoKEM is a key-encapsulation mechanism whose security rests on the plain, unstructured Learning With Errors problem, with no ring or module algebraic structure. It is a lattice-based scheme designed for a conservative security margin: it deliberately forgoes the compact structure that makes ML-KEM efficient, accepting larger keys and slower operations in exchange for a simpler, more heavily studied hardness assumption.

#How it works

FrodoKEM builds a KEM from the standard LWE problem over a large, uniformly random square matrix A in Z_q, where q is a power of two. The public key is the pair (A, B), with B = A S + E for a secret matrix S and a small error matrix E; recovering S from (A, B) is exactly the plain LWE problem. Encapsulation samples fresh small secrets, forms noisy products against A and B, and encodes a random value into the low bits, which the holder of S can recover. An Fujisaki-Okamoto transform wraps this passively secure core into an IND-CCA2 KEM, the same construction pattern ML-KEM uses.

Because A carries no algebraic structure, it must be transmitted or regenerated in full. Each parameter set ships in an AES variant and a SHAKE variant that expand A pseudorandomly from a seed, using AES-128 or SHAKE-128 respectively, so the matrix itself does not have to be sent. The core cost remains a full matrix by matrix multiplication rather than the ring multiplication used by structured schemes.

#The conservative tradeoff

Plain LWE is the oldest and least structured lattice assumption. Efficient designs such as ML-KEM instead use Module-LWE, which adds algebraic structure to shrink keys and speed up arithmetic. No attack is known that breaks the structured variants faster than the plain problem, but some analysts prefer to avoid the extra structure entirely on the theory that it could one day open an avenue for cryptanalysis. FrodoKEM is the design that takes that caution to its conclusion: it pays a large size and speed penalty to depend only on general LWE. Like all lattice KEMs, it resists Grover-style quantum search with only the modest quadratic speedup that larger parameters already absorb.

#Parameters and sizes

FrodoKEM has three parameter sets targeting NIST security categories 1, 3, and 5. Sizes are in bytes, from the specification at frodokem.org; AES and SHAKE variants share these sizes.

For comparison, ML-KEM public keys run 800 to 1568 bytes, roughly an order of magnitude smaller; full figures are in post-quantum algorithm comparison.

#Standardization and status

The scheme originates in the 2016 paper Frodo: Take off the ring!, which showed that a practical LWE key exchange without ring structure was feasible. FrodoKEM entered the NIST PQC process and reached the third round as an alternate candidate, but NIST did not select it for standardization; NIST IR 8413 cited its large sizes and lower performance against the sufficiency of the schemes already chosen.

Development continued outside NIST. FrodoKEM is being standardized through ISO/IEC, and Germany's federal information security agency BSI recommends it in its TR-02102 technical guideline as one of two approved key-encapsulation mechanisms, alongside the code-based Classic McEliece, for profiles that prioritize a conservative assumption over efficiency. That positions FrodoKEM as a deliberate alternative to ML-KEM rather than a competitor for the same deployments: it is chosen where the extra confidence of unstructured LWE is judged worth its bandwidth and speed cost.

#Limitations

The size and speed penalty is intrinsic, not an implementation detail: unstructured LWE cannot be made as compact as a module lattice without changing the assumption. Public keys and ciphertexts on the order of 10 to 20 kilobytes make FrodoKEM awkward for high-volume protocol handshakes and constrained devices, which is why efficiency-focused standards default to ML-KEM. Its appeal is confined to settings that can absorb that cost and want the most conservative lattice foundation available.