NTRU Prime: FAQ

Are small lattice-based cryptosystems patented?

There are no known patent threats against the "Quotient NTRU" lattice proposals: NTRU-HPS (ntruhps), NTRU-HRSS (ntruhrss), and Streamlined NTRU Prime (sntrup). The original NTRU system in the 1990s was patented (U.S. patent 6081597), but the patent holder issued a press release in March 2017 saying that NTRU was free to use. Any questions about the effect of this release were settled when the patent expired in August 2017.

There are known patent threats against the "Product NTRU"/"Ring-LWE"/"LPR" lattice proposals: Kyber, SABER, and NTRU LPRime (ntrulpr). These proposals use a "noisy DH + reconciliation" structure that appears to be covered by U.S. patent 9094189 expiring 2032, and a 2x ciphertext-compression mechanism that appears to be covered by U.S. patent 9246675 expiring 2033. There are also international patents, sometimes with different wording.

Furthermore, the 2015 version of NewHope inspired several further patents on various "Product NTRU"/"Ring-LWE"/"LPR" systems, including Chinese patent 107566121 filed November 2016, Chinese patent 108173643 filed November 2016, Korean patent 101905689 filed November 2016, U.S. patent application 20200169384 filed November 2016, U.S. patent 11050557 filed May 2017, and European patent 3698515 filed October 2017.

Didn't submitters to the NIST competition promise to give up their patents?

Many submitters did, and most submitters did not have patents in the first place, but the holders of the patents threatening the remaining "Product NTRU"/"Ring-LWE"/"LPR" submissions are not the submitters.

Isn't NIST buying out the patents so everyone can use them?

A previous version of this FAQ stated the following: "There have been rumors of buyout talks since mid-2019. Perhaps the buyout talks will be successful, or perhaps the patent holders are spreading these rumors to increase interest in the cryptosystems and thus increase their expected income. Users aware of patent threats tend to switch to alternatives."

FOIA results in May 2021 partially confirmed the rumors. NIST had been in contact with the patent holders for patent 9094189, and in this context had written "We're still mostly waiting for them to give us a number" in January 2021.

A statement from NIST at the Third NIST PQC Standardization Conference in June 2021 appeared to indicate that the buyout talks had failed, specifically because NIST could not afford the amount of money that the patent holders were asking for. (Video, minute 1:08–1:09: "just the ballpark figures that were being mentioned made it clear that this wasn't something NIST was gonna be able to do. It was definitely more than our overall budget for our crypto group".) A statement from NIST on 7 October 2021 said "NIST continues to engage IP holders to discuss applicability and intentions regarding licensing."

How can lattice-based cryptosystems be patented if lattice-based cryptography is from the 1990s?

Every modern proposal for a small lattice-based encryption system shares some features with the original NTRU system but also includes new details. Those details can be the subject of patents, as Product NTRU illustrates.

There are probably some "submarine" patents and patent applications that have not yet been brought to public attention. Patent 9094189 was not widely known within the community until 2018.

Within the Quotient NTRU proposals, sntrup4591761 was published in May 2016; the first version of ntruhrss701 was published in July 2017; the first ntruhps versions were published in December 2017; sntrup761 and the current versions of ntruhrss701 and ntruhps were published in April 2019. The one-way function inside sntrup761 is identical to the one-way function inside sntrup4591761, so the only potential patent risks to sntrup761 are from (1) patents filed after May 2016 covering the small changes made in the CCA transform and (2) earlier patents.

The Product NTRU proposals are generally less stable than the Quotient NTRU proposals, and could be threatened by further patents beyond the patents listed above. The first version of Kyber was published in 2017, a new version was published in April 2019, and a newer version was published in October 2020, including changes to the one-way functions.

Why don't we just use exactly the details published in the 1990s?

Many advances in lattice attacks have been published since then. Lattice designers in the 1990s misjudged the security level of short-vector problems, the safety of decryption failures, etc. Using an old lattice system eliminates patent risks but increases security risks.

Are the known patents going to hold up in court?

The idea of public-key encryption using "noisy DH + reconciliation" is normally credited to Lyubashevsky, Peikert, and Regev. The idea appears in the 2012 full version of the LPR paper, and appeared in LPR talk slides starting in April 2010. However, none of this is early enough to kill the patent. The patent was filed on 18 February 2010.

There have been various unsuccessful efforts to find publications of the LPR cryptosystem predating the patent filing. Noisy DH was published in 2009, but without the reconciliation mechanism needed for encryption. The Eurocrypt 2010 version of the LPR paper was due to the publisher on 26 February 2010, the submitted version of the paper was due in October 2009, and it is conceivable that versions of the paper predating the patent filing were distributed openly enough to qualify as prior art, but the submitted version and the Eurocrypt 2010 version did not present the LPR cryptosystem. Instead they presented a bigger, slower cryptosystem.

Courts can invalidate a patent by declaring that the patented invention was obvious to someone of "ordinary skill in the art". Paragraph 8 of a statement under oath by Peikert claimed that someone "wishing to improve the efficiency" of an LWE-based cryptosystem, and having ordinary skill in the art as of 18 February 2010, would have "arrived at the invention set out in the claims of the patent". But then why did the Eurocrypt 2010 version of the LPR paper, which asks whether "LWE and its applications could be made truly efficient" and which was not due to the publisher until 26 February 2010, present a bigger, slower cryptosystem?

A similar difficulty will appear in any effort to invalidate patent 9246675. The patent was filed in 2012 on an encryption system using noisy DH + low-bandwidth reconciliation. Compared to the LPR cryptosystem, this achieves nearly 2x ciphertext compression at essentially no cost. A 2014 paper from Peikert then claimed, as one of its "main technical innovations" (the only "innovation" highlighted in the abstract), a "low-bandwidth" reconciliation technique that "reduces the ciphertext length" of LPR "nearly twofold, at essentially no cost". If 2x ciphertext compression was already obvious to someone of ordinary skill in the art in 2012, why was it claimed to be a new "innovation" in Peikert's paper in 2014?

A British law firm named Keltie, not saying who was paying it to do this, filed a formal objection to the European version of patent 9094189. All documents in the litigation are online. One document filed by Keltie named three cryptographers working on Keltie's side of the case. One of them was Peikert. Two of them were from the UK NCSC, presumably from GCHQ. The patent was upheld in the first round of litigation. Keltie appealed. After a preliminary assessment from the board of appeals, Keltie withdrew the appeal on 20 October 2021.

Perhaps subsequent litigation regarding these two patents will succeed in eliminating the patents or limiting their coverage. However, today it is far from clear that "Product NTRU"/"Ring-LWE"/"LPR" systems will be free to use before 2033.

Analysis is also required of newer patents, including the flood of patent applications that began in 2016, predating the publication of most submissions to the NIST competition.

Do these patents really apply to Kyber?

Increased awareness of the patent threat has led to three arguments that Kyber does not infringe patents 9094189 and 9246675. The first argument, regarding patent 9246675, claims that Kyber avoids reconciliation. The second argument, regarding patent 9246675, is that Kyber does not drop as many bits per coefficient as the patent does; Kyber's overall compression compared to LPR relies partly on dropping bits and partly on sending fewer coefficients. The third argument, regarding both patents, is that Kyber replaces (e.g.) a 1024-coefficient ring with a rank-4 module over a 256-coefficient ring.

However, in analyzing infringement (and validity) of a patent, it is essential to begin with the definitions and procedures used by patent courts. For example, under the "doctrine of equivalents", the scope of a patent "is not limited to its literal terms but instead embraces all equivalents to the claims described". Festo Corp. v. Shoketsu Kinzoku Kogyo Kabushiki Co., 535 U.S. 722, 732 (2002). The patent holder can show infringement of a patent claim under this doctrine by showing for each element of the claim that "the accused product performs substantially the same function in substantially the same way with substantially the same result". Crown Packaging Tech., Inc. v. Rexam Beverage Can Co., 559 F.3d 1308, 1312 (Fed. Cir. 2009).

It will be straightforward for the patent holders to argue that changing from rings to low-rank modules with similar efficiency is performing substantially the same function in substantially the same way with substantially the same result. The same comment applies to changing from dropping many bits to dropping some bits and dropping some coefficients. Arguments saying that there is a change are missing the point. Furthermore, the claimed dividing line between "reconciliation" and Kyber does not have a clear definition, and it is difficult to see how any proposed definition could avoid the doctrine of equivalents; there is, as Section 6.4.1 of the Kyber submission puts it, "virtually no difference between the two approaches".

There is much more to say about patent law, and it is important to avoid overconfident predictions in any direction. Again, it is possible that litigation will succeed in eliminating these patents or limiting their coverage; but, again, today it is far from clear that "Product NTRU"/"Ring-LWE"/"LPR" systems will be free to use before 2033; and, again, analysis is also required of newer patents.

Why does NTRU Prime say "Quotient NTRU" and "Product NTRU" instead of "NTRU" and "the Ring-LWE cryptosystem"?

The problem of finding small secret ring elements (s,e) given (A,As+e) is a central example of what is now called the Ring-LWE problem. The original NTRU cryptosystem already needed this problem to be difficult. A lattice attack against this problem was already analyzed in Section 3.4.2 of the original NTRU paper as an attack against the cryptosystem.

More broadly, the best attacks known are shared between "NTRU" and "the Ring-LWE cryptosystem". The names "Quotient NTRU" and "Product NTRU" recognize the shared structure of the cryptosystems and allow the attacks exploiting this structure to be simply described as NTRU attacks. Attacks specific to Quotient NTRU or to Product NTRU can be described as such.

Using a completely different "Ring-LWE"/"LPR" name (1) tends to suppress credits to the original NTRU paper and (2) tends to hide the relationships between the cryptosystems. This can be dangerous:

"Hybrid attacks" against "NTRU" were introduced in 2007.
An "LWE" paper years later, not citing the 2007 paper, introduced "decoding attacks", and proposed "Ring-LWE" key sizes of "2-5 kilobits".
In fact, "decoding attacks" are hybrid attacks, but are missing some huge attack speedups from the 2007 paper. Key sizes of "2-5 kilobits" do not reach an acceptable security level.

Today most "Ring-LWE" security analyses continue to ignore state-of-the-art hybrid attacks, while the "NTRU" literature pays closer attention to attacks.

Didn't Google run an experiment with a Product NTRU system, NewHope?

Yes. In July 2016, Google announced an experiment with "CECPQ1", combining an elliptic curve with NewHope. Google wrote that it did not wish to make this algorithm a de-facto standard so it planned "to discontinue this experiment within two years, hopefully by replacing it with something better". Google concluded "While it's still very early days for quantum computers, we're excited to begin preparing for them, and to help ensure our users' data will remain secure long into the future."

A few months later, in November 2016, Google announced that the experiment had concluded. Google then waited until 2019 before beginning an experiment with "CECPQ2", combining an elliptic curve with a variant of NTRU-HRSS.

Why would Google have run an experiment with something if it was patented?

There is no evidence that the authors of NewHope were aware of the patents when they published the first version of their paper. There is no evidence that Google was aware of the patents when it began its CECPQ1 experiment. There are reports of Google having been contacted by one of the patent holders after it began its CECPQ1 experiment. Google has not commented on these patents, and insists that it concluded the experiment for other reasons.

Why hasn't everybody been warning the public about these patent problems?

Most cryptographers working on LPR and its descendants were surprised when they first heard about these patents, because they were not aware of any contributions of the patent holders to their work:

For patent 9094189, it is reasonably clear that the ideas were published independently before anyone heard the ideas from the patent holders. (This does not invalidate the patent, unless the independent publications predated the patent filing.)
For patent 9246675, general awareness of the ideas comes from the 2014 paper, which does not credit the 2012 publications from the patent holder. (The patent holder, in turn, rarely credits the LPR publications. This does not invalidate the patent.)
The newer patents listed above have received so little public attention that there has not even been a preliminary analysis of what, if anything, the patent holders contributed.

People would like to believe that there must be some reason that the patents are invalid or are inapplicable or will disappear, and would like to believe that this overrides the obligation to warn potential users regarding the patents.

The patent holders have a financial incentive to avoid warning potential users before the patented ideas are deployed. Furthermore, for unclear reasons, NIST has discouraged public patent analysis within NISTPQC. For example:

Even though the NISTPQC call for submissions required NIST to collect public statements from submitters regarding patents, NIST's posting of those statements then said "For the 1^st round, all submissions should be evaluated and analyzed on their technical merits." This directly discouraged public patent analysis. The first round continued until 2019.
In response to some subsequent public patent analysis, NIST sent private email to the analyst dated 7 Dec 2020 15:24:16 +0000 stating, among other things, "We hope everyone will focus on the technical issues, rather than on the patents right now."
Even though the call for submissions said that "NIST will perform a thorough analysis of the submitted algorithms in a manner that is open and transparent to the public, as well as encourage the cryptographic community to also conduct analyses and evaluation", NIST never published its own analysis of patent threats. In response to a December 2020 FOIA request related to "patents that apply or potentially apply to various round-3 submissions to the NIST Post-Quantum Cryptography Standardization Project (NISTPQC)", NIST delayed responding until May 2021 and provided only limited information, in particular refusing to provide 3 documents totaling 31 pages. Uncertainty regarding the contents of NIST's secret patent analysis continues to discourage public patent analysis.

For comparison, the call for submissions, under "Intellectual Property Statements / Agreements / Disclosures", states that "NIST believes it is critical that this process leads to cryptographic standards that can be freely implemented in security technologies and products". This is the only use of the word "critical" in the call for submissions.

What's the difference among the Quotient NTRU systems?

Streamlined NTRU Prime, NTRU-HRSS, and NTRU-HPS are small lattice-based systems, specifically Quotient NTRU systems, but this still leaves many choices of details that can affect security and performance. Streamlined NTRU Prime systematically chooses its design details to minimize the complexity of a thorough security review, even if this means sacrificing some speed.

So Streamlined NTRU Prime is much less efficient than NTRU-HRSS and NTRU-HPS?

No. Streamlined NTRU Prime turns out to be very close in performance to NTRU-HRSS and NTRU-HPS, and is even beating them in some benchmarks. There are no known examples of applications where the performance differences matter in either direction (although it is easy to construct artificial examples). The subtitle of the original NTRU Prime paper was "reducing attack surface at low cost".

In more detail, what are the similarities and differences between these systems?

Streamlined NTRU Prime and NTRU-HRSS have always used an irreducible polynomial and avoided decryption failures. NTRU-HPS acquired these features when it merged with NTRU-HRSS to form the round-2 NTRU submission.

The one-way function inside Streamlined NTRU Prime has always been deterministic. NTRU-HRSS and NTRU-HPS added this feature for the round-2 NTRU submission.

The polynomial x^p−x−1 in Streamlined NTRU Prime has a maximum-size "Galois group" (size approximately (p/2.7)^p, superexponential in the degree p), maximizing the cost of computing automorphisms. The polynomial (x^p−1)/(x−1) in NTRU-HRSS and NTRU-HPS is a "cyclotomic" with a minimum-size Galois group (size p−1, same as the degree).

Streamlined NTRU Prime uses a prime modulus q, and further requires the polynomial to remain irreducible modulo q, while NTRU-HRSS and NTRU-HPS use a power-of-2 modulus q. Streamlined NTRU Prime uses "rounding", while NTRU-HRSS and NTRU-HPS use "errors". Streamlined NTRU Prime and NTRU-HPS use "fixed weight", while NTRU-HRSS uses "variable weight".

If the Product NTRU patent problems disappear, isn't Kyber the most efficient lattice KEM?

No. For example, if you require the "pre-quantum Core-SVP" mechanism of claiming security levels to be at least 2¹²⁸, then the smallest ciphertexts available from the parameter sets selected for these lattice KEMs are as follows:

With NTRU Prime: sntrup653 with 897-byte ciphertexts.
With NTRU-HPS: ntruhps2048677 with 931-byte ciphertexts.
With Kyber: kyber768 with 1088-byte ciphertexts.
With SABER: saber with 1088-byte ciphertexts.
With NTRU-HRSS: ntruhrss701 with 1138-byte ciphertexts.

There are security levels where Kyber performs better, and manipulating security cutoffs can hide all cases where Kyber performs worse, but a full comparison shows that Kyber suffers from supporting only a sparse set of security levels.

But Kyber makes up for this by being super-efficient in CPU cycles, right?

No. Kyber is tuned to minimize cycles on large server CPUs, which can somewhat offset its bandwidth disadvantages, but the same tuning turns out to cause problems for Kyber in performance on small platforms, where speed is generally viewed as being more important. The complications of the module structure in Kyber also lose performance.

Kyber has been mathematically proven to be as secure as hard lattice problems, right?

No. There are some ideal-lattice problems that are not broken by any published attacks, and there are some theorems saying that some large lattice cryptosystems are not much less secure than these ideal-lattice problems. Kyber is not big enough for the theorems to apply. Also, the theorems do not say that these ideal-lattice problems are hard: for example, a complete break of cyclotomic ideal-lattice problems would not contradict the theorems.

These proofs are still a qualitative advantage of Kyber, right?

No. The rationale for allowing Kyber to claim such proofs would also allow NTRU-HPS, NTRU-HRSS, Streamlined NTRU Prime, NTRU LPRime, and SABER to claim such proofs. See Section 9 of "Comparing proofs of security for lattice-based encryption".

Kyber has at least been mathematically proven to be no easier to break than NewHope, right?

No. This is misinformation in NIST IR 8309. There is no hope of such a proof.

I've heard that NTRU Prime measures security levels differently from everyone else! Is this true?

No. NIST made clear during round 1 of NISTPQC that it wanted all lattice submissions to use the "Core-SVP" mechanism of claiming security levels, so the round-2 and round-3 NTRU Prime submissions report Core-SVP.

The NTRU Prime submission also provides the most comprehensive survey ever published of problems with Core-SVP. This survey includes three problems that appear to be quantitatively severe (ignoring the cost of memory, ignoring hybrid attacks, ignoring enumeration) and many more problems that could be severe. The submission computes various alternatives to Core-SVP designed to address these three problems. The differences between mechanisms of estimating security are clearly labeled.

I've heard that NTRU Prime chose parameters more aggressively than everyone else! Is this true?

No. The minimum pre-quantum Core-SVP level that NTRU Prime allows in its selected parameter sets is 2¹²⁹, and sntrup761 (2¹⁵³) is recommended for an extra security margin. NTRU-HPS, Kyber, and SABER were allowed into round 3 of NISTPQC with selected parameter sets having pre-quantum Core-SVP levels 2¹⁰⁶, 2¹¹¹, and 2¹²⁵. The 2¹²⁵ for SABER turned out to be a calculation error: the correct number is 2¹¹⁸. In round-3 tweaks announced in October 2020, Kyber eliminated its 2¹¹¹ parameter set on security grounds and selected a less efficient 2¹¹⁸ parameter set.

See "A discretization attack" (September 2020) and Section 7.2 of "NTRU Prime: round 3" (October 2020) for detailed analyses of NIST's inconsistent handling of security levels. NIST has not responded to the content of the analyses. NIST stated a year later (October 2021) that "we disagree that we have been inconsistent in handling security categories, or any suggestion that we are favoring one submission more than another".

Are other cryptographers concerned about cyclotomic lattices?

41% of the lattice-based submissions in NISTPQC round 1 (December 2017 through January 2019) provided options that do not rely on cyclotomic structure. Most of the 41% paid heavily in performance for these options; the only exceptions were Three Bears (which still relied on small Galois groups) and NTRU Prime. Most of the 41% expressed concerns regarding security. Most of the 41%—for example, Frodo and Titanium, from submitters with many years of lattice publications—provided no options relying on cyclotomic structure.

This is not the story of a community confident in the security of cyclotomic lattices. On the contrary, a large fraction of the community considered cyclotomic lattices sufficiently risky to justify putting serious work into unstructured lattices as a backup plan. Meanwhile Titanium and NTRU Prime offered alternatives. NTRU Prime was and is the only submission using a large Galois group while remaining competitive in performance with cyclotomics.

NIST IR 8309 refers to NIST's "confidence in cyclotomic structures". NIST has not explained its rationale for this confidence.

What is the status of NTRU Prime in the NIST competition?

NIST selected 15 submissions for round 3 of the NIST Post-Quantum Standardization Project, including 7 "finalists" and 8 "alternates". NIST IR 8309 states the following:

NIST intends to select a small number of the finalists for standardization at the end of the third round. In addition, NIST expects to standardize a small number of the alternate candidates (most likely at a later date).

NTRU Prime is one of the "alternate" candidates.

How do I cite this FAQ page?

Citation in BibTeX format:

@misc{ntruprimefaq,
  author={NTRU Prime FAQ team},
  title={{FAQ}},
  url={https://ntruprime.cr.yp.to/faq.html},
  note={Accessed 1 January 2025}
}

Make sure to edit the date appropriately.

Version: This is version 2022.03.03 of the "FAQ" web page.