ROUND 2 OFFICIAL COMMENT: Frodo

[D. J. Bernstein]

The latest NIST report states that Frodo in TLS key exchange would cost
"around 20,000 bytes" plus "2 million cycles" for the server. NIST
appears to conclude from this that Frodo does not have "acceptable
performance in widely used applications overall".

I'm filing this comment to request explanation of the basis for NIST's
claim that 20000 bytes plus 2 million cycles would not be "acceptable
performance" for post-quantum TLS key exchange.

Google said (https://www.imperialviolet.org/2018/04/11/pqconftls.html)
that the unstructured-lattice size is "probably not preferable for
real-time TLS connections". This does not justify NIST's black-and-white
claim that the size isn't "acceptable". The words "real-time" are also
important: there are many ways to avoid having a user wait for a key
exchange. Google documented software bugs causing problems with these
sizes for a particular way of integrating post-quantum crypto into TLS,
but this can be worked around.

I should note that the above claim is my understanding of what NIST is
saying regarding Frodo performance, but the text is somewhat ambiguous:

The resulting potential security advantages of Frodo are paid for
with far worse performance in all metrics than other lattice schemes.
... Use of FrodoKEM would have a noticeable performance impact on
high traffic TLS servers, where each server does decapsulation which
requires close to 2 million cycles for the best performing parameter
set (FrodoKEM-640-AES) and receives a public key and a ciphertext
(around 20,000 bytes in total) for every fresh key exchange.

In NIST’s view, FrodoKEM may be suitable for use cases where the high
confidence in the security of unstructured lattice-based schemes is
much more important than performance. NIST’s first priority for
standardization is a KEM that would have acceptable performance in
widely used applications overall. As such, possible standardization
for FrodoKEM can likely wait until after the third round.

This doesn't _directly_ say that TLS is the "widely used application" in
which Frodo doesn't have "acceptable performance", so perhaps NIST meant
something else, but then it's weird that TLS is the only example given.

---Dan

P.S. It's also worrisome to see NIST expressing "high confidence in the
security of unstructured lattice-based schemes", as if the claimed
asymptotic lattice security levels weren't 42% higher just 10 years ago
and superexponentially higher just 20 years ago. Asking for the basis
for NIST's claims regarding acceptable application performance should
not be interpreted as endorsing overconfident security claims.

[Perlner, Ray A. (Fed)]

Dear Dan,

While it is not possible to speak for what every user of our standards would or wouldn’t find “acceptable”, there is a pretty large difference between the performance of Frodo on the one hand and Kyber, NTRU, and Saber on the other hand. We are therefore more confident that Kyber, NTRU, or Saber will be considered “acceptable” for most users than that Frodo will.