Streamlined NTRU Prime Security Considerations
draft-josefsson-cfrg-sntrup-considerations-00
This document is an Internet-Draft (I-D).
Anyone may submit an I-D to the IETF.
This I-D is not endorsed by the IETF and has no formal standing in the
IETF standards process.
| Document | Type | Active Internet-Draft (individual) | |
|---|---|---|---|
| Author | Simon Josefsson | ||
| Last updated | 2026-06-22 | ||
| RFC stream | (None) | ||
| Intended RFC status | (None) | ||
| Formats | |||
| Stream | Stream state | (No stream defined) | |
| Consensus boilerplate | Unknown | ||
| RFC Editor Note | (None) | ||
| IESG | IESG state | I-D Exists | |
| Telechat date | (None) | ||
| Responsible AD | (None) | ||
| Send notices to | (None) |
draft-josefsson-cfrg-sntrup-considerations-00
Network Working Group S. Josefsson, Ed.
Internet-Draft 22 June 2026
Intended status: Informational
Expires: 24 December 2026
Streamlined NTRU Prime Security Considerations
draft-josefsson-cfrg-sntrup-considerations-00
Abstract
This document contains considerations for use of the Streamlined NTRU
Prime Post-Quantum Key Encapsulation Method (KEM). The document is
intended as introduction and guidance to encourage adoption of
Streamlined NTRU Prime in IETF standards-track protocols.
About This Document
This note is to be removed before publishing as an RFC.
Status information for this document may be found at
https://datatracker.ietf.org/doc/draft-josefsson-cfrg-sntrup-
considerations/.
Source for this draft and an issue tracker can be found at
https://gitlab.com/jas/ietf-ntruprime.
Status of This Memo
This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
This Internet-Draft will expire on 24 December 2026.
Copyright Notice
Copyright (c) 2026 IETF Trust and the persons identified as the
document authors. All rights reserved.
Josefsson Expires 24 December 2026 [Page 1]
Internet-Draft sntrup Security Considerations June 2026
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents (https://trustee.ietf.org/
license-info) in effect on the date of publication of this document.
Please review these documents carefully, as they describe your rights
and restrictions with respect to this document. Code Components
extracted from this document must include Revised BSD License text as
described in Section 4.e of the Trust Legal Provisions and are
provided without warranty as described in the Revised BSD License.
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2
2. Sources . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Functionality . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1. API overview . . . . . . . . . . . . . . . . . . . . . . 4
3.2. Parameter sizes . . . . . . . . . . . . . . . . . . . . . 4
3.3. Parameter options . . . . . . . . . . . . . . . . . . . . 5
4. Security . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4.1. Cryptosystem security goals and basis for confidence . . 5
4.2. Quantitative security levels . . . . . . . . . . . . . . 7
4.3. Implementation security . . . . . . . . . . . . . . . . . 7
4.4. Error-free APIs . . . . . . . . . . . . . . . . . . . . . 8
5. Hybrid usage . . . . . . . . . . . . . . . . . . . . . . . . 9
6. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 9
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
8. References . . . . . . . . . . . . . . . . . . . . . . . . . 9
8.1. Normative References . . . . . . . . . . . . . . . . . . 9
8.2. Informative References . . . . . . . . . . . . . . . . . 9
Author's Address . . . . . . . . . . . . . . . . . . . . . . . . 10
1. Introduction
This document reviews information available for protocol designers
and implementors considering usage of Streamlined NTRU Prime
(sntrup), a post-quantum public-key cryptosystem.
Among currently supported lattice-based KEMs, sntrup is the most
stable option. All of the sntrup details stabilized in an April 2019
publication. Any QROM IND-CCA2 attack against the KEM tightly
implies an attack against the one-wayness of an underlying lattice
function. The underlying lattice function was published in May 2016.
sntrup has never needed a security patch.
https://libntruprime.cr.yp.to (https://libntruprime.cr.yp.to)
[libntruprime-website] summarizes further features of sntrup and
provides open-source production-quality sntrup software with a very
simple stateless API. The library includes various positive tests,
negative tests, and constant-time tests, along with source-level
Josefsson Expires 24 December 2026 [Page 2]
Internet-Draft sntrup Security Considerations June 2026
timing defenses described in https://cr.yp.to/papers/cryptoint-
20250424.pdf (https://cr.yp.to/papers/cryptoint-20250424.pdf). The
library is available as a package in Debian and in Debian-derived
distributions such as Ubuntu.
Streamlined NTRU Prime is specified and deployed for the Secure Shell
(SSH) protocol, see [RFC9941]. https://ssh-
comparison.quendi.de/comparison/kex.html (https://ssh-
comparison.quendi.de/comparison/kex.html) indicates that every major
SSH implementation supports sntrup761x25519-sha512@openssh.com.
Rollout of sntrup761x25519-sha512@openssh.com already began in 2022,
making sntrup the post-quantum KEM most likely to interoperate with
deployed SSH peers as of 2026. (Note that it is generally
recommended for SSH implementations to support multiple options.)
https://ianix.com/pqcrypto/pqcrypto-deployment.html
(https://ianix.com/pqcrypto/pqcrypto-deployment.html) includes
further examples of sntrup deployment.
2. Sources
The NTRU Prime team site is https://ntruprime.cr.yp.to
(https://ntruprime.cr.yp.to) [NTRUPrime-website].
https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf
(https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf)
[NTRUPrime-spec] includes the authoritative definition of sntrup, a
design rationale, and a security analysis.
https://ntruprime.cr.yp.to/ntruprime-20200930.sage
(https://ntruprime.cr.yp.to/ntruprime-20200930.sage) [NTRUPrime-sage]
is the reference implementation in Sage (Python plus math libraries)
of sntrup.
https://ntruprime.cr.yp.to/nist/ntruprime-20190330.pdf
(https://ntruprime.cr.yp.to/nist/ntruprime-20190330.pdf) is the
earlier April 2019 publication of the complete sntrup KEM.
https://ntruprime.cr.yp.to/ntruprime-20160511.pdf
(https://ntruprime.cr.yp.to/ntruprime-20160511.pdf) is the May 2016
publication of the underlying lattice function, which is designed to
be one-way.
(The May 2016 specification also includes a complete KEM
sntrup4591761. The April 2019 sntrup has different details of
hashing and encoding to handle all sntrup sizes, such as sntrup761
and sntrup1277, in a unified way. This document does not cover the
earlier sntrup4591761 design.)
Josefsson Expires 24 December 2026 [Page 3]
Internet-Draft sntrup Security Considerations June 2026
https://cr.yp.to/papers/latticeproofs-20190719.pdf
(https://cr.yp.to/papers/latticeproofs-20190719.pdf) reviews the
literature showing that any QROM IND-CCA2 attack against sntrup
tightly implies a one-wayness attack against the underlying lattice
problem.
3. Functionality
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 (https://bench.cr.yp.to/results-kem.html):
+============+==================+==================+=============+
| System | ciphertext bytes | public-key bytes | private-key |
| | | | bytes |
+============+==================+==================+=============+
| sntrup653 | 897 | 994 | 1518 |
+------------+------------------+------------------+-------------+
| sntrup761 | 1039 | 1158 | 1763 |
+------------+------------------+------------------+-------------+
| sntrup857 | 1184 | 1322 | 1999 |
+------------+------------------+------------------+-------------+
| sntrup953 | 1349 | 1505 | 2254 |
+------------+------------------+------------------+-------------+
| sntrup1013 | 1455 | 1623 | 2417 |
+------------+------------------+------------------+-------------+
| sntrup1277 | 1847 | 2067 | 3059 |
+------------+------------------+------------------+-------------+
Table 1
Josefsson Expires 24 December 2026 [Page 4]
Internet-Draft sntrup Security Considerations June 2026
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 (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
(https://eprint.iacr.org/2023/1298) and
https://eprint.iacr.org/2025/1520 (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 (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. Security
4.1. Cryptosystem security goals and basis for confidence
https://ntruprime.cr.yp.to (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."
Josefsson Expires 24 December 2026 [Page 5]
Internet-Draft sntrup Security Considerations June 2026
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 (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 (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
(https://blog.cr.yp.to/20140213-ideal.html)), before decryption
failures were used for attacks in https://eprint.iacr.org/2019/1308
(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 (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 (https://arxiv.org/abs/1503.03107) and
https://eprint.iacr.org/2016/957 (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
(https://ntruprime.cr.yp.to/latticerisks-20211031.pdf) is a newer
survey of security risks in lattice-based cryptosystems.
Josefsson Expires 24 December 2026 [Page 6]
Internet-Draft sntrup Security Considerations June 2026
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
(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
(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
(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
(https://eprint.iacr.org/2025/1910) and
https://eprint.iacr.org/2026/279 (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
(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
(https://blog.cr.yp.to/20240102-hybrid.html) reports 156 lines for
X25519 with the same streamlining. Lattice software is larger and
Josefsson Expires 24 December 2026 [Page 7]
Internet-Draft sntrup Security Considerations June 2026
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
(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.
Josefsson Expires 24 December 2026 [Page 8]
Internet-Draft sntrup Security Considerations June 2026
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
(https://ntruprime.cr.yp.to/nist/ntruprime-
20201007.pdf#subsection.2.2).
5. Hybrid usage
Streamlined NTRU Prime may be used in conservative constructs
together with other KEMs in a hybrid mode, see Chempat
[I-D.josefsson-chempat] for one way to combine Streamlined NTRU Prime
with other key agreement methods, such as X25519.
6. Acknowledgments
The editor would like to thank various NTRU Prime Team members for
contributions to this document.
7. IANA Considerations
This document has no IANA actions.
8. References
8.1. Normative References
[NTRUPrime-spec]
NTRU Prime Team, "NTRU Prime: round 3", October 2020,
<https://ntruprime.cr.yp.to/nist/ntruprime-20201007.pdf>.
8.2. Informative References
[I-D.josefsson-chempat]
Josefsson, S., "Chempat: Generic Instantiated PQ/T Hybrid
Key Encapsulation Mechanisms", Work in Progress, Internet-
Draft, draft-josefsson-chempat-04, 20 October 2025,
<https://datatracker.ietf.org/doc/html/draft-josefsson-
chempat-04>.
Josefsson Expires 24 December 2026 [Page 9]
Internet-Draft sntrup Security Considerations June 2026
[libntruprime-website]
Daniel J. Bernstein, "libntruprime Website", October 2022,
<https://libntruprime.cr.yp.to/>.
[NTRUPrime-sage]
NTRU Prime Team, "NTRU Prime Sage script", September 2020,
<https://ntruprime.cr.yp.to/ntruprime-20200930.sage>.
[NTRUPrime-website]
NTRU Prime Team, "NTRU Prime Website", October 2022,
<https://ntruprime.cr.yp.to/>.
[RFC9941] Friedl, M., Mojzis, J., and S. Josefsson, "Secure Shell
(SSH) Key Exchange Method Using Hybrid Streamlined NTRU
Prime sntrup761 and X25519 with SHA-512:
sntrup761x25519-sha512", RFC 9941, DOI 10.17487/RFC9941,
April 2026, <https://www.rfc-editor.org/rfc/rfc9941>.
Author's Address
Simon Josefsson (editor)
Email: simon@josefsson.org
Josefsson Expires 24 December 2026 [Page 10]