FrodoKEM is a lattice-based key encapsulation mechanism that uses plain Learning With Errors (LWE) instead of the structured Module-LWE that ML-KEM uses. The "plain" choice makes Frodo's keys an order of magnitude larger than ML-KEM's, but it also gives Frodo the most conservative security analysis of any production-ready lattice KEM. If a future attack ever breaks structured lattices (Ring-LWE or Module-LWE) without affecting plain LWE, FrodoKEM is the scheme that survives.
NIST evaluated FrodoKEM in Rounds 1 and 2 of the post-quantum competition but did not advance it to Round 3. ISO/IEC subsequently standardised FrodoKEM in ISO/IEC 18033-2 amendments, giving it international standardisation status even without NIST FIPS certification. This article explains what FrodoKEM is, why it survived even though NIST passed on it, and where it fits in 2026.
The Plain English Edition
Imagine you have two ways to write a secret. One way uses a special grammar that compresses your message to a single line of code. The other way uses ordinary English, taking up an entire page. The single-line code is faster to read and write, but if someone breaks the special grammar, they read your secret immediately. The page-long English version is slower, but breaking it requires solving a much harder problem.
ML-KEM is the special grammar (Module-LWE). FrodoKEM is the page-long English (plain LWE). Both are believed quantum-secure. The difference is that the structured lattice approach (ML-KEM) has more compact representations and faster operations, while plain LWE has the simplest, most studied security proof.
The LWE Family Tree
Learning With Errors (LWE) was introduced by Oded Regev in 2005. It became the foundation for almost all modern lattice cryptography. Three flavours emerged over time:
- Plain LWE: Unstructured matrices. Simplest analysis, largest keys.
- Ring-LWE: Polynomials in a single ring. Smaller keys, more structure to analyse.
- Module-LWE: Modules over a small ring. Middle ground. ML-KEM uses this.
FrodoKEM uses plain LWE. The "Frodo" name is a wink at Lord of the Rings (a "ring" puns the lattice ring structure that Frodo deliberately avoids). The original paper by Bos, Costello, Ducas, Mironov, Naehrig, Nikolaenko, Raghunathan, and Stebila, "Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE", was published at CCS 2016.
The Conservative Argument
The argument for plain LWE goes: structured lattices have more algebraic structure, and that structure could in theory be exploited by a future cryptanalyst. Plain LWE has no such structure to exploit. If someone finds a polynomial-time attack on Ring-LWE or Module-LWE, the world still has plain LWE as a fallback.
This is not a hypothetical concern. Several published attacks have improved cryptanalysis on structured lattices over the years (BKZ improvements, dual-lattice variants, sub-field attacks against Ring-LWE with specific parameter shapes). None of these attacks have broken Ring-LWE at standardised parameter sets, but they suggest the structured-lattice family is a more active attack target than plain LWE.
FrodoKEM Parameter Sets
The Round 2 FrodoKEM submission (the latest before NIST elimination) had three security levels:
| Parameter set | Security level | Public key size | Ciphertext size | Decryption error |
|---|---|---|---|---|
| FrodoKEM-640 | NIST Category 1 | 9,616 bytes | 9,720 bytes | 2^-138 |
| FrodoKEM-976 | NIST Category 3 | 15,632 bytes | 15,744 bytes | 2^-199 |
| FrodoKEM-1344 | NIST Category 5 | 21,520 bytes | 21,632 bytes | 2^-252 |
Compared to ML-KEM-768 (1,184-byte public key, 1,088-byte ciphertext), FrodoKEM-976 is about 13x larger in both directions. Compared to Classic McEliece (1 MB public key), FrodoKEM is much smaller, especially in the public key.
For most TLS handshakes, a 15 KB public key is too large. Frodo fits scenarios where the keys are pre-distributed or where bandwidth is not the dominant cost.
The AES vs SHAKE Variants
FrodoKEM has two pseudo-random matrix-generation variants. The AES variant uses AES-128 in counter mode to expand a seed into the public matrix. The SHAKE variant uses SHAKE-128. Both are constant-time and verifiable, but they perform differently on different hardware. AES-NI on modern Intel CPUs makes the AES variant about 2x faster than SHAKE, while platforms without AES-NI prefer SHAKE because it has a simpler hardware footprint. The two variants produce different parameter sets and key encodings, so an implementation has to commit to one.
Why NIST Passed on FrodoKEM
NIST's Round 2 evaluation (July 2020) eliminated FrodoKEM, advancing CRYSTALS-Kyber, NTRU, and Saber as the lattice KEM finalists. The official rationale (NIST IR 8309) cited:
- Performance gap: FrodoKEM was about 10x slower than Kyber and Saber on most platforms. The plain-LWE matrix arithmetic is more expensive than the structured-lattice operations.
- Bandwidth gap: 13x larger keys made Frodo unfit for typical TLS scenarios.
- Diversity already covered: NIST had decided to keep one lattice candidate plus non-lattice alternates (Classic McEliece, BIKE, HQC). The non-lattice alternates provide diversity. A second lattice candidate did not add as much diversity as a code-based or hash-based alternate.
NIST did not say FrodoKEM was insecure. The decision was about whether the bandwidth and performance cost of plain LWE was worth the conservative security argument. NIST decided no, picking structured-lattice schemes plus non-lattice alternates instead.
ISO Standardisation
FrodoKEM was adopted by ISO/IEC 23837-2 (a draft amendment to ISO/IEC 18033-2 covering post-quantum encryption). The international body kept FrodoKEM in their standards portfolio precisely for the conservative-diversity argument. ISO has historically been more cautious about cryptographic schemes than NIST, and the plain-LWE pedigree appealed to that caution.
For organisations that follow ISO rather than (or in addition to) NIST, FrodoKEM is a viable option in 2026.
Where FrodoKEM Lives Now
FrodoKEM has reference implementations in:
- liboqs (Open Quantum Safe), as a research-grade option.
- Microsoft Research's PQCrypto-VPN project, which uses FrodoKEM for some experimental deployments.
- Several academic security suites for teaching post-quantum cryptography.
- Some German government pilot projects that follow BSI guidance, where BSI has historically expressed cautious support for FrodoKEM as a conservative option.
The deployment scenarios are niche but real. Pre-shared key scenarios, long-term archival, ISO-compliant systems, and conservative-design deployments where the bandwidth cost is acceptable.
FrodoKEM vs ML-KEM: When to Choose Which
The trade-off looks like this:
| Factor | FrodoKEM | ML-KEM (Kyber) |
|---|---|---|
| Standardisation | ISO/IEC, BSI cautious | NIST FIPS 203 (final) |
| Public key size | 9-22 KB | 800-1,568 bytes |
| Ciphertext size | 9-22 KB | 768-1,568 bytes |
| Performance | 10x slower | Faster |
| Security assumption | Plain LWE | Module-LWE |
| Conservative pedigree | Strongest | Strong |
| Library support | Limited | Broad |
| Regulatory adoption | Niche | Mainstream |
For most production deployments in 2026, ML-KEM is the right choice. FrodoKEM enters the picture only when:
- ISO compliance is required and NIST FIPS is insufficient.
- The deployment has minimal bandwidth constraints.
- The customer specifically wants the most conservative possible lattice security.
- The keys are pre-distributed and not exchanged in-band.
FrodoKEM in QNSQY
QNSQY does not ship FrodoKEM. The scheme is not FIPS-standardised, and QNSQY ships only NIST FIPS-standardised algorithms by default. ML-KEM is the lattice KEM in all tiers; HQC provides non-lattice diversity in Business tier.
If a customer requires FrodoKEM specifically (for example, an ISO-compliant medical device deployment in a jurisdiction that does not accept NIST FIPS as sufficient), QNSQY's hybrid envelope format is extensible. This would be a Business tier conversation requiring custom key-management procedures.
FrodoKEM's bandwidth profile is genuinely problematic for QNSQY's typical use case, which is encrypting files for one or more recipients. A 15 KB public key per recipient adds up quickly when sharing files with teams of 10 or 20 people. ML-KEM's 1.2 KB public keys keep the key-bundle manageable. HQC sits in between (about 7-14 KB ciphertexts). The choice to centre the portfolio on ML-KEM is partly about ensuring the user experience does not collapse under bandwidth weight as recipient counts grow.
The Conservative Diversity Argument
FrodoKEM's continued relevance in 2026 reflects a broader pattern in post-quantum cryptography: institutions disagree about how much to value conservative pedigree.
- NIST prioritises performance and standardisation timeline. Result: ML-KEM.
- ISO/IEC values conservative diversity. Result: FrodoKEM in their standards.
- NSA's CNSA 2.0 is NIST-aligned for symmetric and asymmetric, but takes hash-based signatures (XMSS, LMS) for firmware. The hash-based choice is the conservative diversity slot in the signature space.
For QNSQY's threat model (hospital and military-grade), the conservative diversity slot is HQC for KEMs and SLH-DSA for signatures. FrodoKEM is not in the portfolio because HQC's smaller bandwidth makes it more practical, and HQC has the NIST FIPS standardisation that QNSQY's regulated customers require.
Where Plain LWE Does Show Up
FrodoKEM is not entirely absent from production cryptography. Several research-grade and government pilot deployments use it:
- The German Federal Office for Information Security (BSI) has expressed cautious openness to FrodoKEM as an option for organisations that want a more conservative profile than NIST FIPS provides. BSI has not mandated FrodoKEM but lists it among acceptable post-quantum options in their guidance.
- Microsoft Research has produced extensive FrodoKEM tooling, including FPGA implementations, Open Quantum Safe integration, and benchmarking suites. Their PQCrypto-VPN project uses FrodoKEM in some configurations.
- Academic teaching contexts prefer FrodoKEM as a pedagogical example of plain LWE because the algorithm is simpler to explain than the structured-lattice variants.
The deployment pattern is "ISO-aligned, not NIST-aligned, with a conservative twist". For organisations whose threat model genuinely demands the most conservative possible lattice scheme and whose bandwidth budget can absorb 15 KB keys, FrodoKEM is a real option. For everyone else, ML-KEM is the right answer.
For more on the broader landscape of conservative options, see Classic McEliece Deep Dive, HQC Explained, and Lattice-Based Cryptography Explained.
Frequently Asked Questions
Is FrodoKEM secure?
Yes. FrodoKEM has been studied since 2016 and has no known catastrophic attacks. The plain-LWE foundation is one of the oldest and most studied lattice problems in cryptography. NIST eliminated FrodoKEM in Round 2 for performance and bandwidth reasons, not security weakness.
Could a quantum computer break FrodoKEM?
Not at standardised parameter sets. The best known quantum attacks give only modest speedups over classical attacks for plain LWE. The Category 5 parameter set (FrodoKEM-1344) targets the 256-bit security level with adequate margin against known quantum algorithms.
Why are FrodoKEM keys so much larger than ML-KEM keys?
Because plain LWE uses unstructured matrices. The public key contains a full random-looking matrix and a vector, totaling many thousands of bytes. Module-LWE compresses this by structuring the matrix as a small module over a polynomial ring. The structure shrinks the representation by an order of magnitude at the cost of slightly less conservative security analysis.
Is FrodoKEM in any major protocol?
Not as a default. Some experimental TLS deployments and some German government pilots have used FrodoKEM. Most production protocols default to ML-KEM. ISO standardisation gives FrodoKEM a path for non-US-NIST deployments, but the network effect is much smaller than ML-KEM's.
Sources
- Bos, J., Costello, C., Ducas, L., Mironov, I., Naehrig, M., Nikolaenko, V., Raghunathan, A., Stebila, D. "Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE." ACM CCS 2016. https://eprint.iacr.org/2016/659
- NIST. "Status Report on the Second Round of the NIST Post-Quantum Cryptography Standardization Process." NIST IR 8309, July 2020. https://csrc.nist.gov/pubs/ir/8309/final
- NIST. "Module-Lattice-Based Key-Encapsulation Mechanism Standard." FIPS 203, August 13, 2024. https://csrc.nist.gov/pubs/fips/203/final
- Regev, O. "On lattices, learning with errors, random linear codes, and cryptography." STOC 2005, JACM 2009. https://cims.nyu.edu/~regev/papers/qcrypto.pdf
- Alkim, E., Bos, J. W., Ducas, L., Easterbrook, K., LaMacchia, B., Longa, P., Mironov, I., Naehrig, M., Nikolaenko, V., Peikert, C., Raghunathan, A., Stebila, D. "FrodoKEM: Learning With Errors Key Encapsulation, Round 3 submission." 2021. https://frodokem.org/files/FrodoKEM-specification-20210604.pdf
- ISO/IEC 23837-2. "Information technology - Security techniques - Test requirements for cryptographic modules - Part 2: Post-quantum encryption." Draft amendment status. https://www.iso.org/standard/77078.html
Related Articles
- ML-KEM Explained
- Lattice-Based Cryptography Explained
- Classic McEliece Deep Dive
- HQC Explained
- NIST FIPS Guide for Post-Quantum Standards
Protect Your Data Before Q-Day Arrives
QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats.