NTRU Prime

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.

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 Product NTRU/Ring-LWE/LPR are not the submitters.

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

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.

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?

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. The patent was upheld. An appeal is ongoing. All documents in the litigation are online.

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 in 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 in February 2010, and it was conceivable that this version was distributed openly enough to qualify as prior art before the patent was filed, but this version did not present the LPR cryptosystem: it 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". However, if the LPR cryptosystem was obvious to someone of ordinary skill in the art in February 2010, then why did a bigger, slower cryptosystem appear in the Eurocrypt 2010 version of the LPR paper?

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?

Perhaps the appeal regarding 9094189, and subsequent litigation regarding both patents, will succeed in eliminating these 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.

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:

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, bceause they were not aware of any contributions of the patent holders to their work:

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.

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.

The one-way function inside Streamlined NTRU Prime has always been deterministic. NTRU-HRSS and NTRU-HPS acquired this feature in 2019.

The polynomial xp−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 (xp−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 2128, then the smallest ciphertexts available from the parameter sets selected for these lattice KEMs are as follows:

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 false advertising 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 2129, and sntrup761 (2153) 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 2106, 2111, and 2125. The 2125 for SABER turned out to be a calculation error: the correct number is 2118. In round-3 tweaks announced in October 2020, Kyber eliminated its 2111 parameter set on security grounds and selected a less efficient 2118 parameter set.

See "NTRU Prime: round 3" and "A discretization attack" for detailed analyses of NIST's inconsistent handling of security levels.

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.

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