# NTRU vs ML-KEM: Why Lattice Won the Race **Source**: https://quantumsequrity.com/blog/ntru-vs-ml-kem **Category**: PQC Algorithms --- [← Back to Blog](../../blog) PQC Algorithms # NTRU vs ML-KEM: Why Lattice Won the Race 10 min read NTRU and ML-KEM are both lattice-based key encapsulation mechanisms, both quantum-resistant, both NIST Round 3 finalists. NTRU has been around since 1996, longer than every other surviving post-quantum scheme except McEliece. ML-KEM, derived from CRYSTALS-Kyber, was finalised as FIPS 203 on August 13, 2024. NIST chose ML-KEM, not NTRU. This article explains why. The short answer is patents, security analysis, and the difference between two flavours of lattice problem. The long answer covers thirty years of cryptographic engineering, two NIST competitions, and a mathematical detail (the difference between NTRU's quotient-ring lattice and ML-KEM's module lattice) that turns out to matter for both performance and assurance. ## The Two Flavours of Lattice Imagine a city where every building is at the corner of two streets. If the streets are perfectly aligned at right angles, you can describe any building's address with two numbers: how far east, how far north. That is a lattice in two dimensions. Cryptographic lattices are the same idea in 256 or 768 dimensions. Hard problems on these lattices, like finding the building closest to a target point, are believed to resist both classical and quantum attack. NTRU and ML-KEM both use lattice math, but they shape the lattice differently. NTRU works in a single quotient ring, where vectors are polynomials reduced modulo `x^n + 1` and a small integer modulus. ML-KEM works with modules over a smaller ring, stacking small polynomial vectors in a structured grid. The difference looks technical but has practical consequences for key sizes, ciphertext sizes, and the security reduction proofs. ## NTRU's Origin: 1996, Hoffstein, Pipher, Silverman The original NTRU paper, "NTRU: A ring-based public key cryptosystem", was presented at ANTS-III in 1998 by Jeffrey Hoffstein, Jill Pipher, and Joseph Silverman, all then at Brown University. The construction had been circulating since 1996 and the founders started a company, NTRU Cryptosystems, to commercialise it. NTRU was the first public-key system to break free of the integer-factorisation and discrete-logarithm assumptions that underpin RSA and ECC. Its security rested on the shortest vector problem in a structured lattice, a problem that had no known polynomial-time algorithm even on a quantum computer. In 1996, that "even on a quantum computer" line was prophetic: Peter Shor had published his factoring algorithm only two years earlier, and the cryptographic community was still figuring out what post-quantum even meant. ### Patents and the Lost Decade NTRU Cryptosystems held several patents on the scheme through the late 1990s and 2000s. The patents made many cryptographers reluctant to deploy or even study the algorithm closely. Open-source projects steered clear, academic textbooks gave it a paragraph rather than a chapter, and most security engineers learned about NTRU only as a footnote. The patents began expiring in the late 2010s. By 2017, the most fundamental patents had lapsed and Onboard Security (which had acquired NTRU Cryptosystems) released the core algorithm under a Creative Commons license. The patent overhang is a major reason NTRU never achieved the deployment momentum of RSA or ECDSA in its first two decades, even though the math was sound. ## ML-KEM's Origin: 2017, CRYSTALS-Kyber CRYSTALS-Kyber was submitted to NIST in November 2017 by a team including Joppe Bos, Léo Ducas, Eike Kiltz, Tancrède Lepoint, Vadim Lyubashevsky, John M. Schanck, Peter Schwabe, Gregor Seiler, and Damien Stehlé. The "CRYSTALS" name was a portmanteau for "CRYptographic Suite for Algebraic LatticeS", and Kyber was the KEM half of the suite (Dilithium, now ML-DSA, was the signature half). Kyber's security rested on the Module Learning With Errors (MLWE) problem, a generalisation of plain LWE that uses small modules over a ring. The module structure gave Kyber three key benefits over plain LWE: smaller keys, faster computation, and easier parameter scaling between security levels. NIST flagged these as significant practical advantages in IR 8413. ### Why Module-LWE Beats Ring-LWE Beats LWE Plain LWE (the FrodoKEM approach) uses unstructured matrices, giving the most conservative security analysis but the largest keys (around 9 KB for 128-bit security). Ring-LWE compresses everything to a single polynomial ring, shrinking keys to under 1 KB but introducing structure that some cryptographers worry about. Module-LWE sits in between: a small module over a small ring. The module structure is conservative enough to dodge concerns about deep ring algebra attacks, while still allowing sub-1KB keys. NTRU sits in a different corner. It uses a single quotient ring, similar in shape to ring-LWE, but the security reduction goes via the NTRU lattice rather than LWE. Both shapes are believed hard, and neither has been broken in the parameter ranges NIST evaluated. But the security reductions are different, and NIST has historically preferred reductions that connect cleanly to standard worst-case lattice problems. ## The NIST Process: Round 1 to Round 3 When NIST opened the post-quantum competition in 2017, NTRU was actually two distinct submissions, NTRU Prime (Bernstein et al.) and NTRU (Hoffstein et al.). They were merged in Round 2 (January 2019). Kyber was a standalone submission throughout. By Round 3 (July 2020), the lattice KEM finalists were CRYSTALS-Kyber, NTRU, and Saber. The conservative non-lattice alternates were Classic McEliece, BIKE, and HQC. NIST asked the world to keep cryptanalysing all three lattice candidates with full intensity. ### What NIST Saw in Round 3 NIST's IR 8413 final report from July 2022 explained the selection rationale in unusual detail. Key points: - **Performance**: Kyber's encryption was about 1.5x faster than NTRU's at comparable security levels. The advantage came from Kyber's NTT-friendly modulus (3329) and the simpler module structure. - **Patent freedom**: By 2022, both NTRU and Kyber were patent-free, but NTRU's patent history made some implementers nervous about future submarine claims. Kyber had no such overhang. - **Security reduction**: Kyber's reduction to MLWE was tighter than NTRU's reduction to its own lattice problem. Both schemes were considered secure, but the proofs differed in clarity. - **Diversity**: NIST wanted only one lattice KEM. The non-lattice alternatives (Classic McEliece, BIKE, HQC) were moved to Round 4 to provide algorithmic diversity. This made the lattice slot a winner-takes-all contest. In July 2022, NIST announced Kyber as the winner. NTRU was not selected, ending a 26-year journey from research curiosity to almost-standard. ## Kyber Becomes ML-KEM (FIPS 203) NIST published the FIPS 203 Initial Public Draft in August 2023 and finalised it on August 13, 2024. The renamed scheme is ML-KEM, "Module-Lattice-Based Key-Encapsulation Mechanism Standard". The cryptographic core matches Kyber Round 3 with a few adjustments: - **Three parameter sets** named by security level: ML-KEM-512 (Category 1, ~AES-128), ML-KEM-768 (Category 3, ~AES-192), ML-KEM-1024 (Category 5, ~AES-256). - **Key sizes**: ML-KEM-768 has a public key of 1,184 bytes and a ciphertext of 1,088 bytes. NTRU at the same security level (NTRU-HPS-2048-509) had a public key of 699 bytes but a ciphertext of 699 bytes, so NTRU's total bandwidth was lower per session. - **Implicit rejection** in decapsulation, which gives stronger CCA security guarantees and resistance to chosen-ciphertext attacks. - **Domain separation hash labels** added throughout the spec to make implementations harder to misuse. For more detail on what shipped, see [ML-KEM Explained](ml-kem-explained). ## Where NTRU Lives Now NTRU is not dead. Several real-world deployments use it. OpenSSH still ships an NTRU mode (`sntrup761x25519-sha512`, originally NTRU Prime hybrid), enabled by default in OpenSSH 9.0 and later. The Tor network uses an NTRU variant in its hybrid handshake. The Streamlined NTRU Prime variant has been formally analysed and continues to be a mature, ready-for-production scheme. The IETF has not produced an RFC for NTRU specifically, but the algorithm is on the same maturity tier as Kyber for practical engineering. The reason most new standards point at ML-KEM and not NTRU is institutional: NIST FIPS 203 is the binding document for US federal procurement, and most international bodies (ISO, ETSI, BSI) follow NIST's lead within a year or two of the standard. ### NTRU's Strengths NIST Did Not Pick For some scenarios, NTRU still has real advantages. Its ciphertexts are smaller (699 vs 1,088 bytes at Category 3). Its key generation is faster than ML-KEM's. Its implementation surface is smaller, since it does not need an NTT for full performance. In bandwidth-constrained or constrained-implementation settings, NTRU remains a defensible choice. But for general-purpose key encapsulation in TLS, IKEv2, MLS, and post-quantum hybrid schemes, ML-KEM is now the default. ## NTRU and ML-KEM in QNSQY QNSQY ships ML-KEM (sizes 512, 768, 1024) as its primary post-quantum KEM in all tiers. Free tier is limited to ML-KEM-512 in hybrid mode with X25519. Pro tier allows all three ML-KEM sizes. Business tier additionally allows pure post-quantum KEM (no X25519 backup) for users who require strict NIST-only chains, and adds [HQC](hqc-explained), still pre-standard, as a non-lattice alternate. QNSQY does not ship NTRU, on the same rationale NIST applied: only one lattice KEM, and that one lattice KEM is the FIPS 203 winner. Customers who need NTRU specifically (for example, an existing OpenSSH-based migration) should use OpenSSH's `sntrup761x25519-sha512` mode for transport, with QNSQY for at-rest file encryption. ### The Single-KEM Discipline Shipping multiple lattice KEMs in one product would create operational complexity without meaningful security benefit. If both NTRU and ML-KEM eventually fall to the same hypothetical lattice attack, having both in the suite saves nothing. If only one falls, having both is useful but only if the unbroken one happens to be the right diversity hedge. Statistically, NIST's choice of HQC (code-based) and SLH-DSA (hash-based) as the conservative non-lattice options provides better diversity than two lattice KEMs. This is why QNSQY's portfolio is structured around mathematical-family diversity, not within-family redundancy. ML-KEM is the lattice KEM and HQC, still pre-standard, the code-based KEM. SLH-DSA and LMS are the hash-based signatures, and ML-DSA and the pre-standard FN-DSA the lattice signatures. For key establishment, QNSQY ships one lattice KEM, not two. ## Frequently Asked Questions ### Is NTRU broken? No. NTRU has not been broken at any of its standardised parameter sets. The original 1996 paper survived three NIST evaluation rounds and continues to be considered secure against both classical and quantum attack. NIST simply preferred Kyber (now ML-KEM) for the FIPS 203 slot for the reasons above. ### Should I migrate from NTRU to ML-KEM? If you have an NTRU deployment that is meeting your needs, there is no security reason to rip it out. If you are designing a new system in 2026 or later, ML-KEM is the default choice because it is the federal standard, the international ISO track is following, and library support is broader. See [Hybrid Encryption Explained](hybrid-encryption) for combining either with classical primitives. ### What is the difference between NTRU and NTRU Prime? NTRU Prime is a 2016 variant by Daniel J. Bernstein and collaborators that avoids certain ring-of-integers structures from the original NTRU. The two were submitted separately to NIST and merged in Round 2. The Streamlined NTRU Prime variant is what OpenSSH uses today. The differences are about which polynomial ring is used, not about whether the scheme is secure. ### Why does ML-KEM use such a strange modulus (3329)? The number 3329 is prime and has a 256th root of unity, which lets ML-KEM use a very fast Number Theoretic Transform (NTT) for polynomial multiplication. NTRU traditionally used a power-of-two modulus (2048 or similar), which is simpler but does not admit the NTT speedup. The NTT is a major reason ML-KEM beats NTRU on signing/verifying throughput. See [Lattice-Based Cryptography Explained](lattice-based-cryptography-explained) for more. ## Sources 1. NIST. "Module-Lattice-Based Key-Encapsulation Mechanism Standard." FIPS 203, August 13, 2024. https://csrc.nist.gov/pubs/fips/203/final 2. NIST. "Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process." NIST IR 8413, July 2022. https://csrc.nist.gov/pubs/ir/8413/final 3. Hoffstein, J., Pipher, J., Silverman, J. H. "NTRU: A ring-based public key cryptosystem." Algorithmic Number Theory, ANTS-III, 1998. https://www.math.brown.edu/jhs/Preprints/HPS96.pdf 4. Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J. M., Schwabe, P., Seiler, G., Stehlé, D. "CRYSTALS-Kyber: A CCA-Secure Module-Lattice-Based KEM." IEEE EuroS&P, 2018. https://eprint.iacr.org/2017/634 5. Bernstein, D. J., Brumley, B. B., Chen, M.-S., Chuengsatiansup, C., Lange, T., Marotzke, A., et al. "NTRU Prime: round 3 specification." NIST PQC submission, October 2020. https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf 6. NIST. "Module-Lattice-Based Digital Signature Standard." FIPS 204, August 13, 2024. https://csrc.nist.gov/pubs/fips/204/final ## Related Articles - [ML-KEM Explained](ml-kem-explained) - [Lattice-Based Cryptography Explained](lattice-based-cryptography-explained) - [NIST FIPS Guide for Post-Quantum Standards](nist-fips-guide) - [Hybrid Encryption Explained](hybrid-encryption) - [What Is Post-Quantum Cryptography?](what-is-post-quantum-cryptography) --- ### Protect Your Data Before Q-Day Arrives QNSQY's NIST-standardized post-quantum encryption protects files against both current and quantum-era threats. [Try QNSQY](../../pricing)