Streamlined NTRU Prime Security Considerations

3.1. API overview

sntrup is a family of key-encapsulation mechanisms (KEMs). Each parameter set specifies one KEM in the family. Each KEM provides three operations: keygen produces a public key and private key; enc produces a session key and ciphertext given a public key; dec produces a session key given a ciphertext and a private key.¶

Session keys are 32 bytes. Applications typically use session keys as keys for an authenticated cipher to encrypt and authenticate user data, or as message-authentication keys if messages are public.¶

3.2. Parameter sizes

The NTRU Prime documentation selects six parameter sizes for support. The following numbers are extracted from https://bench.cr.yp.to/results-kem.html:¶

In libntruprime, a unified code generator produces software for all of the supported sizes. It is recommended to reduce risks from advances in lattice attacks by choosing the largest supported size that fits into the application. For most applications, this means sntrup1277.¶

Comparison to alternatives: The graph in https://ntruprime.cr.yp.to/latticerisks-20211031.pdf#page.42 compares sizes and claimed security levels of several lattice options from 2021. The sizes are overall similar, but the details show that the smallest sizes within those options are sometimes sntrup and sometimes alternatives, depending on the target security level. Post-2021 NTRU variants such as https://eprint.iacr.org/2023/1298 and https://eprint.iacr.org/2025/1520 provide smaller sizes. Some of the available options are limited to a few parameter sets because of internal cryptosystem constraints.¶

3.3. Parameter options

NTRU Prime includes not just sntrup but also ntrulpr (NTRU LPRime), an alternative that shares most lines of code with sntrup. However, this document focuses on sntrup and recommends choosing sntrup rather than ntrulpr.¶

(https://ntruprime.cr.yp.to/latticerisks-20211031.pdf#subsection.1.5.8 explains one disadvantage of the LPR approach to small lattice-based systems: all known theorems for those cryptosystems allow QROM IND-CCA2 security of the KEMs to be many bits weaker than one-wayness of the underlying lattice functions.)¶

The sntrup caller uses keygen, enc, and dec on byte-string objects for the public key, private key, and ciphertext. Each parameter set specifies the lengths of these byte strings. Internal details of these objects are included in the sntrup specification and are not exposed to the caller. Callers do not choose their own encodings.¶

4.1. Cryptosystem security goals and basis for confidence

https://ntruprime.cr.yp.to says that "Streamlined NTRU Prime is a small lattice-based KEM aiming for the standard goal of IND-CCA2 security."¶

The main argument for confidence in lattice-based cryptosystems is that there are many papers studying the cost of lattice attacks. However, the NTRU Prime documentation questions this confidence. The documentation describes risks of lattice-based cryptosystems. The documentation also describes ways that sntrup reduces these risks. https://cr.yp.to/talks/2019.08.24/slides-djb-20190824-ntruprime-4x3.pdf summarizes the sntrup design approach as follows:¶

• Within lattice systems: Focus on structured lattice systems for "applications that want something much smaller" than unstructured lattices.¶

• Within structured lattice systems: "Eliminate unnecessarily complicated security review: eliminate decryption failures, eliminate cyclotomics, etc."¶

• Within that constraint: "Optimize size vs. security against known attacks".¶

https://ntruprime.cr.yp.to says that lattice-based cryptography "has an extremely complicated attack picture with many different attack tools, many losses of security, and many security claims that turned out to be wrong ... Streamlined NTRU Prime is systematically designed to minimize the complexity of a thorough security review ... The success of the proactive Streamlined NTRU Prime design strategy is illustrated by subsequently published decryption-failure attacks violating the security claims of LAC and Round5."¶

Eliminating "decryption failures" is one of the features included in the first description of NTRU Prime (https://blog.cr.yp.to/20140213-ideal.html), before decryption failures were used for attacks in https://eprint.iacr.org/2019/1308, https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/round-1/official-comments/Round5-official-comment.pdf, etc. Eliminating "cyclotomics" is another feature of the 2014 description of NTRU Prime, before https://arxiv.org/abs/1503.03107 and https://eprint.iacr.org/2016/957 broke Gentry's original STOC 2009 lattice-based FHE system for cyclotomics. https://ntruprime.cr.yp.to/latticerisks-20211031.pdf is a newer survey of security risks in lattice-based cryptosystems.¶

4.2. Quantitative security levels

There are many bits of uncertainty regarding the costs of specific lattice attacks. For example, the final Kyber documentation https://web.archive.org/web/20230310174959/https://pq-crystals.org/kyber/data/kyber-specification-round3-20210804.pdf estimated "2^151^ gates" to break Kyber-512 but said that "this number could be affected by a factor of up to 2^16^ in either direction" because of "known unknowns".¶

Furthermore, https://ntruprime.cr.yp.to/nist/ntruprime-20171130.pdf says that "the best attack algorithms known today are much better than the best attack algorithms known a few years ago, so it is unreasonable to expect that the algorithms have stabilized".¶

https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf#page.103 reports security estimates for the selected NTRU Prime parameters. The same document emphasizes that "advances in attacks could reduce costs below the actual costs of known attacks (which in turn could be above or below current estimates of the costs of known attacks)".¶

Newer speedups include https://eprint.iacr.org/2025/1910 and https://eprint.iacr.org/2026/279. The costs of lattice attacks remain uncertain and unstable. This motivates taking the largest supported parameters that fit into the application.¶

4.3. Implementation security

https://cr.yp.to/papers/pqcomplexity-20240419.pdf analyzes the complexity of reference implementations of Kyber, NTRU-HPS, NTRU-HRSS, and NTRU Prime, after uniform streamlining of the implementations. For example, it finds 497 lines for kyber512, 472 lines for kyber1024, 578 lines for a merge of kyber512 and kyber1024, 478 lines for sntrup761, 478 lines for sntrup1277, 484 lines for a merge of sntrup761 and sntrup1277, 385 lines for ntruhrss701, 381 lines for ntruhps4096821, and 452 lines for a merge of ntruhrss701 and ntruhps4096821.¶

https://blog.cr.yp.to/20240102-hybrid.html reports 156 lines for X25519 with the same streamlining. Lattice software is larger and more likely to contain bugs: lattice software is usually newer than ECC software, and the community has less experience with the types of bugs to expect. (Formal verification can convincingly eliminate bugs, but post-quantum software is currently only partially verified.) ECC+PQ double encryption reduces the impact of PQ bugs and of other PQ security problems.¶

https://libntruprime.cr.yp.to/security.html includes descriptions of specific implementation security issues relevant to NTRU Prime: "For example, there are some CPUs, especially embedded CPUs, where integer multiplication takes variable time. Most software for public-key cryptography relies on integer multiplication, although there are exceptions such as code-based cryptography."¶

Cryptographic software is presumably breakable if the computer's RNG is weak, if other parts of the computer leak RNG data or other internal cryptosystem data, if attackers can access physical sensors such as electromagnetic sensors close to the computer, or if attackers have enough control over the computer to create faults in computations. Commonly discussed mitigations include recomputations to address physical faults, "masking" and "hiding" to reduce physical leakage of secret data, zeroing secrets after the secrets are used, combining multiple RNGs, centralizing RNGs for auditability, fixing security problems elsewhere in the computer, and isolating sensitive computations on separate devices.¶

4.4. Error-free APIs

libntruprime provides error-free APIs for keygen, enc, and dec.¶

Most KEMs, including sntrup, build dec internally on top of a simpler decryption mechanism. For "implicit rejection" KEMs, including sntrup, ciphertexts rejected by the internal decryption mechanism produce pseudorandom KEM session keys, not KEM errors.¶

For some KEMs, the internal decryption mechanism occasionally rejects valid ciphertexts. The sender and receiver then occasionally end up with different session keys, normally triggering failures in higher-level protocols even when there are no KEM API errors. A KEM that reports a very small probability of these "decryption failures" might still be vulnerable to "failure boosting" attacks that search for valid ciphertexts that are more likely to fail and that deduce secret keys from the pattern of failures. For sntrup, the internal decryption algorithm is guaranteed to work for all valid ciphertexts; this is a theorem with a short proof in https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf#subsection.2.2.¶