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
- SVP algorithms,
- 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 cyclotomic rings ("NTRU Classic" rings and "NTRU NTT" rings) to "NTRU Prime" rings, as explained in the original NTRU Prime paper. However, we emphasize that lattice-based cryptography has many other attack avenues that need further study.
Warnings regarding NISTPQC lattice candidates
Beyond the general warnings above, we issue the following more specific warnings to potential users of lattice-based encryption systems submitted to the NIST Post-Quantum Cryptography Standardization Project:
- The Product NTRU lattice submissions (usually labeled as "Ring-LWE" or "LPR") are threatened by two lines of US and international patents.
- Most of the lattice submissions have cyclotomic lattices as options. These options will be broken if cyclotomic lattices are broken. For many of these systems, cyclotomic lattices are the only options.
- Most of the lattice submissions have occasional decryption failures. There are theorems stating that sufficiently rare decryption failures do not reduce security, but most of the submissions have failure rates high enough to break all known theorems. In some cases the claimed failure rates have not been proven, and the actual failure rates could be much higher.
- None of the lattice submissions have proofs that breaking the standard IND-CCA2 security goal is as difficult as inverting the underlying PKE. Available proof techniques are limited to "QROM" IND-CCA2 attacks (or further limited to "ROM" IND-CCA2 attacks), and there has been little study of the possibility of non-QROM IND-CCA2 attacks.
- The Product NTRU lattice submissions do not even have proofs that breaking QROM IND-CCA2 is as difficult as inverting the underlying PKE. The underlying problem is that these submissions rely on "derandomization". All known proofs are compatible with the possibility that derandomization loses many bits of security.
- The Quotient NTRU lattice submissions could lose security because of their quotient structure.
- The Product NTRU lattice submissions could lose security because they release more "samples" than the Quotient NTRU submissions.
- All of the lattice submissions have new details (2017 or newer) that could compromise security and that require security review. For example, the Round2 submission was first published in 2017 and was shown in 2020 to be very efficiently breakable.
- All of the lattice submissions have lower security levels against the best attacks known in 2020 than they had against the best attacks known in 2017. This does not mean that the submissions are breakable, but it means that the security picture is not stable.
Given the general complexity of lattice attacks, the number of different targets, and the fact that new lattice attacks are continuing to appear, it is clear that a few years are not enough time for comprehensive security review.
Regarding small round-3 NISTPQC lattice-based encryption systems in particular,
sntrup is Streamlined NTRU Prime
ntrulpr is NTRU LPRime:
|non-QROM IND-CCA2 attacks||risk||risk||risk||risk||risk|
All of these systems include details first published in 2019, requiring careful security review. All of these systems have lower security levels against the best attacks known in 2020 than they had against the best attacks known in 2017.
NTRU Prime is relatively stable among NISTPQC lattice-based submissions: it has an identical family of one-way functions throughout round 1, round 2, and round 3, and an identical family of CCA transforms throughout round 2 and round 3. However:
- 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.
- Second-round tweaks for the CCA transforms for Streamlined NTRU Prime and NTRU LPRime were first published in April 2019. These tweaks are meant to add extra layers of defense but require careful security review.
Warnings regarding software in general
Beyond the warnings above regarding the definitions of cryptographic functions, we issue further warnings regarding software meant to implement those functions.
At the moment, the most concise implementations of lattice-based cryptography are implementations in the Sage computer-algebra system. However, these implementations leak secret information through timing.
C implementations are sometimes designed
- to avoid data-dependent branches and array indices (for example, conditional swaps are computed by arithmetic rather than by branches) and
- to avoid other C operations that often take variable time (for example, divisions by 3 are computed via multiplications and shifts).
Our C implementations for NTRU Prime are designed this way.
there are at least some platforms where multiplications take variable time,
and fixing this requires platform-specific effort;
C compilers generally do not make any guarantees regarding timing.
Compiled implementations need to be reviewed for constant-time behavior.
The TIMECOP tools automatically review compiled implementations for constant-time behavior. The C implementations for NTRU Prime pass TIMECOP with several different compiler options. However, other compiler options could break constant-time behavior, and there are ways that variable-time behavior could escape TIMECOP.
Implementations also need to be reviewed for correctness. There is a close match between the structure of
- the NTRU Prime specification,
- the NTRU Prime Sage reference implementation, and
- the NTRU Prime C reference implementation,
but this is only the starting point for review; it does not mean that adequate review has taken place. Furthermore, optimized implementations require extra review work. There are many examples of cryptographic software where tests, even quite expensive tests, fail to catch bugs.
SUPERCOP's checksums of outputs from the C implementations of NTRU Prime match checksums computed by pure Sage software, but this does not guarantee that the implementations match on other inputs, and it does not rule out the possibility of bugs shared between the implementations. There are automated tools verifying that some subroutines work correctly for all inputs, but other subroutines still need verification.
Version: This is version 2020.10.31 of the "Warnings" web page.