NTRU Prime

Warnings regarding cryptosystems

[latticerisks] 99pp. (PDF) NTRU Prime Risk-Management Team. "Risks of lattice KEMs." Date: 2021.10.31.

Lattice-based cryptography is much more risky than commonly acknowledged. This applies, in particular, to lattice KEMs under consideration within the NIST Post-Quantum Cryptography Standardization Project (NISTPQC) as of October 2021. The above document

submissionNTRUNTRU PrimeSABERKyberFrodo
KEM familyntruhrssntruhpssntrupntrulprsaberkyberfrodo
KEM7014096122912771277fire1024640
Basics
pk+ct bytes22763684391438222784313619336
ct bytes1138184218471975147215689720
errorsNoisyNoisyRoundedRoundedRoundedNoisyNoisy
Q or PQuotientQuotientQuotientProductProductProductProduct
modulus81924096787978798192332932768
dimension70012281277127710241024640
first 2-norm21.622.622.220.739.232.052.4
second 2-norm21.628.629.229.275.032.052.4
log_2(Core-SVP)136301270271260256150
ct/log_2 ratio8.46.16.87.35.76.164.8
Known attack avenues not ruled out by theorems
latticesriskriskriskriskriskriskrisk
derandomizationriskriskriskrisk
decryption failures165174138
structured latticesriskriskriskriskriskrisk
cyclotomicsriskriskriskrisk
reducibilityriskriskriskrisk
quotientsriskriskrisk
extra samplesriskriskriskrisk
non-QROM FOriskriskriskriskriskriskrisk
non-QROM 2riskriskriskrisk
Known patent threats
patent 9094189riskriskrisk
patent 9246675riskriskrisk
Systemic risks
PKE instability2019.042019.042016.052017.122019.042020.102019.04
instability2019.042019.042019.042019.042019.042020.102019.04

Warnings regarding software

Beyond the warnings above regarding the definitions of cryptographic functions, the following warnings are 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

The C implementations for NTRU Prime are designed this way. However, there are at least some platforms where multiplications take variable time, and fixing this requires platform-specific effort; see https://www.bearssl.org/ctmul.html and https://research.tue.nl/en/studentTheses/a-performance-study-of-x25519-on-cortex-m3-and-m4. Furthermore, 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

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, and automated tools verifying that some of the vectorized subroutines match the reference subroutines for all inputs, but other subroutines still need verification.


Version: This is version 2021.10.31 of the "Warnings" web page.