[TLS] PQC key exchange sizes

[Thom Wiggers <[e-mail]>]

Hi all,

In yesterday’s working group meeting we had a bit of a discussion of the
impact of the sizes of post-quantum key exchange on TLS and related
protocols like QUIC. As we neglected to put Kyber’s key sizes in our slide
deck (unlike the signature schemes), I thought it would be a good idea to
get the actual numbers of Kyber onto the mailing list.

Note that in the context of TLS’s key exchange, the public key would be
what goes into the ClientHello key_shares extension, and the ciphertext
would go into the Server’s ServerHello key_shares extension.

Kyber512: NIST level I, "strength ~AES128"
  public key: 800 bytes
  ciphertext: 768 bytes
  secret key: 1632 bytes
Kyber768: NIST level III, "~AES192"
  public key: 1184
  ciphertext: 1088
  secret key: 2400 bytes
Kyber1024: NIST level V, "~AES256"
  public key: 1568
  ciphertext: 1568
  secret key: 3168

So for the key exchange at least, it seems to me Kyber512 should work for
TLS and QUIC just fine; Kyber768 might be a bit of a squeeze if you want to
stay in QUIC’s default 1300 byte initial packet? Also, I don't really know
how the D of DTLS might change the story.

All the numbers we reported are as of the latest version of the individual
submissions (except as discussed below). The standards that NIST eventually
names FIPS-xyz might have (mildly) different sizes. NIST has said that
they’re always happy to receive feedback and information about use cases
and constraints.

Lastly, Bas Westerbaan has talked about a Kyber draft in yesterday’s CFRG
meeting. I believe a stated goal is to use that for coordinating any
experiments before the NIST standard is out. So keep an eye out if that
interests you.

Cheers,

Thom

PS: Let me also correct the mistake I had introduced in the SPHINCS+
numbers in the TLS talk: SPHINCS+ has indeed gotten slightly smaller than
the numbers I reported. The smallest SPHINCS+ variant (sphincs+-128s) has a
signature size of 7,856 bytes. There’s a nice table with the different
parameter sets of SPHINCS+ on their Github repository
https://github.com/sphincs/sphincsplus#parameters. I’m glad that people
were paying attention, apparently more than I was :-)

I will also clarify that when we mentioned that Falcon needs very careful
attention when implementing, this concerns Falcon's signing routines. These
require constant-time double-width floating point maths; on many CPUs this
will need to be emulated in software. Verification, on the other hand, is a
lot less sensitive.