Re: ROUND 2 OFFICIAL COMMENT: NTRU
Moody, Dustin (Fed)
Dan,
In response to your two points in your official comment on NTRU.
1) You dispute what NISTIR 8309 says about NTRU
Reading your paper for further information, this seems to be disputing the sentences in our NTRU write-up that said "While NTRU is very efficient, it is not quite at the level of the highest-performing lattice schemes" and "NTRU has a small performance gap in comparison to KYBER and SABER". NTRU, Kyber, and SABER are all based on structured lattices and have very good performance. In our report, we wanted to highlight some of the differences between them. Thus the report noted: "In particular, NTRU has slower key generation than the schemes based on RLWE and MLWE." We did not do a detailed dive into all possible application scenarios. We agree that there are scenarios where NTRU could outperform Kyber or SABER. And note - we did select NTRU as a finalist along with Kyber and SABER.
2) You requested more transparency to know if NIST was subjected to a "discretization attack."
NIST certainly strives to run our PQC standardization process in an open and transparent way. We welcome suggestions to improve. However, we do not believe that a discretization attack took place, and don't feel we need to respond to claims of one. We looked at a variety of performance numbers when assessing the 2nd round candidates, and considered them from different viewpoints. When comparing similar candidates, the selections we make are always going to be subjective to some degree, and we understand not everybody will agree with them. These minor disagreements should not be interpreted as a failure of the NIST PQC process.
Dustin
From: D. J. Bernstein
Sent: Friday, September 18, 2020 4:21 AM
To: pqc-comments
Cc: pqc-forum
Subject: ROUND 2 OFFICIAL COMMENT: NTRU
NSA-exploitable weakness in some standardization processes:
https://cr.yp.to/papers.html#categories
The NISTPQC process has exactly this weakness. The paper uses NTRU vs.
Kyber as a case study, showing the results of hypothetical pro-NTRU and
pro-Kyber discretization attacks. The paper also identifies claims in
NIST IR 8309 regarding NTRU that match the results of a hypothetical
pro-Kyber discretization attack and that do not match the facts. I am
therefore filing this OFFICIAL COMMENT to
(1) dispute what NIST IR 8309 says regarding NTRU and
(2) request transparency regarding the NISTPQC process so that the
public can see whether a discretization attack was carried out.
Full details appear in the paper.
---Dan
P.S. My question "What exactly has NSA told NIST regarding NISTPQC,
regarding security levels or otherwise?" (email dated 2 Aug 2020
11:50:26 +0200) remains unanswered.
D. J. Bernstein
from NIST IR 8309 regarding the round-2 submissions: NTRU "is not quite
at the level of the highest-performing lattice schemes" and "has a small
and sometimes worse. The claims do not say this; they are blanket claims
that NTRU is "not quite at the level" of the others.
I request that NIST clearly admit for the record that these claims from
NIST IR 8309 are false.
Regarding content, the claims are disproven by, e.g., the following
numbers (quoted from https://cr.yp.to/papers.html#categories), which are
also regarding the round-2 submissions:
* "Consider an application that requires Core-SVP to be at least
2^128. NTRU's ntruhps2048677 meets this requirement with 931-byte
ciphertexts, while Kyber's kyber768 needs 1088-byte ciphertexts."
(Also, in this situation SABER needs 1088-byte ciphertexts.)
* "An application limited to 1024-byte ciphertexts obtains a
comfortable-sounding 2^145 Core-SVP from NTRU and only 2^111
Core-SVP from Kyber." (Also, in this situation SABER claimed only
2^125, never mind the subsequent correction saying only 2^118.)
Again, if NIST had instead written that NTRU outperforms Kyber and SABER
in _some_ ways and not in _other_ ways, then the contradiction would
have disappeared, but that isn't what NIST wrote. If NIST had expanded
its comparison to include NTRU Prime (the first NIST IR 8309 quote above
is ambiguous on this point but the second quote isn't), then the 2^128
would favor NTRU Prime but the 1024 would still favor NTRU, so the
claims would still be wrong.
Regarding procedures, I already filed an OFFICIAL COMMENT in September
to (inter alia) "dispute what NIST IR 8309 says regarding NTRU". In
response, NIST took the following steps to dodge admitting error:
(1) Saying that it "did not do a detailed dive into all possible
application scenarios".
Is this supposed to be suggesting that it's hard to imagine
applications "limited to 1024-byte ciphertexts"? That it's hard
to imagine applications asking for "Core-SVP to be at least
2^128"? That it's okay for NIST to make false blanket claims if
it hasn't taken enough time to see any of the (many) exceptions?
(2) Pointing to NTRU's "slower key generation".
Under a security requirement of (e.g.) Core-SVP >= 2^128, Kyber
and SABER outperform NTRU in key-generation time. However, under
the same security requirement, NTRU outperforms Kyber and SABER
in (e.g.) ciphertext size.
The dispute isn't about the existence of performance metrics
where Kyber and SABER outperform NTRU. The dispute is about
NIST's exaggerations.
(3) Saying that scenarios exist where NTRU "could" outperform Kyber
"or" SABER.
This is not the same as clearly admitting that NTRU _does_
outperform Kyber and SABER for, e.g., ciphertext size in
applications asking for Core-SVP to be at least 2^128. This is
also not the same as clearly admitting error in NIST IR 8309.
Readers who take the time to go through the details can see that NIST is
wrong, but this isn't a substitute for a clear statement from NIST
admitting that it's wrong. It's bad enough that these and other errors
appeared in NIST IR 8309 in the first place; having the errors corrected
for the record shouldn't require this much effort.
---Dan