Warnings regarding lattice-based cryptography in general
A 2015 algorithm breaks dimension-N SVP (under plausible assumptions) in time 2(c+o(1))N as N→∞ with c≈0.292. For comparison, the best algorithm known just five years earlier had a much worse c≈0.415, and the best algorithm known just ten years before that took time 2Θ(N log N).
Gentry's original FHE system at STOC 2009, with standard "cyclotomic" choices of rings, is now known (again under plausible assumptions) to be broken in polynomial time by a quantum algorithm. Peikert claimed in 2015 that the weakness in Gentry's system was specific to Gentry's short generators and inapplicable to Ideal-SVP:
Although cyclotomics have a lot of structure, nobody has yet found a way to exploit it in attacking Ideal-SVP/BDD... For commonly used rings, principal ideals are an extremely small fraction of all ideals... The weakness here is not so much due to the structure of cyclotomics, but rather to the extra structure of principal ideals that have short generators.
However, the attack was then combined with further features of cyclotomics to break Ideal-SVP (again under plausible assumptions) with approximation factor 2N1/2+o(1), a terrifying advance compared to the previous 2N1+o(1).
As these attack examples illustrate, the security of lattice-based cryptography is not well understood. There are serious risks of further advances in
algorithms that exploit the "approximation factors" used in cryptography,
algorithms that exploit the structure of cryptographic problems such as LWE,
algorithms that exploit the multiplicative structure of efficient cryptographic problems such as Ring-LWE,
algorithms that exploit the structure of these problems for the specific rings chosen by users, and
algorithms to break cryptosystems without breaking these problems.
To eliminate some tools used in recent attacks, we recommend switching from "NTRU Classic" rings and "NTRU NTT" rings to "NTRU Prime" rings, as explained in our paper. However, we emphasize that lattice-based cryptography has many other attack avenues that need further study.
Warnings regarding Streamlined NTRU Prime and NTRU LPRime
Beyond the general warnings above, we issue the following specific warnings to potential users:
Many details of Streamlined NTRU Prime were first published in May 2016 and require careful security review.
Many details of NTRU LPRime were first published in December 2017 and require careful security review.
Our C software was first published in August 2017 (Streamlined NTRU Prime) and December 2017 (NTRU LPRime). The software requires careful security review beyond the review of the cryptosystems per se. See
ref/READMEin the software.
Version: This is version 2017.12.06 of the "Warnings" web page.