Subject: [TLS] TLS 1.3 PQ Cert Performance Study

From: "Panos Kampanakis (pkampana)" <[email-masked]>
Date: Tue, 3 Mar 2020 04:17:46 +0000

Hi all, 

As the topic of PQ certs in TLS has been discussed in this forum a number of
times, I wanted to bring up our paper (https://eprint.iacr.org/2020/071 )
that just appeared in NDSS 2020 for awareness.  

It evaluates the NIST PQ Signature candidates used in X.509 certificates for
TLS 1.3 authentication. At least two algorithms (Dilithium, Falcon) seem to
perform 5-10% slower than classic RSA and ECDSA which does not seem too bad.
The rest are slower mostly because they introduce extra-round trips (when
the TCP initcwnd is set to 10MSS) to the handshake. As we did not test
optimized code at the time, some of the schemes seem a little worse than
they can be, but the results would not deviate by a lot even with the
optimizations when 10MSS initcwnd is in place at the server. For WebPKI, one
algorithm (Falcon) seems better because it is more likely to produce cert
chains <10MSS. When talking SCTs and OCSP staples, there are better options
with small signatures, big public keys and fast verification, if verifiers
can support more than one PQ algorithms. 

Regardless of algorithm, if the cert chain has more than two ICAs, it is
likely to introduce a round-trip (for initcwnd=10MSS). In that case we make
the argument that ICA cert suppression (5.1.3 of draft-rescorla-tls-ctls or
draft-thomson-tls-sic) could save an extra round-trip. Section VII includes
a discussion on implications and integration with existing protocols.

Note that we do not make assertions on the security of any of the schemes or
other implications. We also did not explore performance in lossy
environments and parts of the world that have slow connections. 

Rgs,
Panos