Douglas Stebila

Benchmarking post-quantum cryptography in TLS

Network emulation experiment, key exchange scenario: handshake completion time (median and 95th percentile) vs. packet loss at shorter round-trip times

Abstract

Post-quantum cryptographic primitives have a range of trade-offs compared to traditional public key algorithms, either having slower computation or larger public keys and ciphertexts/signatures, or both. While the performance of these algorithms in isolation is easy to measure and has been a focus of optimization techniques, performance in realistic network conditions has been less studied. Google and Cloudflare have reported results from running experiments with post-quantum key exchange algorithms in the Transport Layer Security (TLS) protocol with real users' network traffic. Such experiments are highly realistic, but cannot be replicated without access to Internet-scale infrastructure, and do not allow for isolating the effect of individual network characteristics.

In this work, we develop and make use of a framework for running such experiments in TLS cheaply by emulating network conditions using networking features of the Linux kernel. Our testbed allows us to independently control variables such as link latency and packet loss rate, and then examine the impact on TLS connection establishment performance of various post-quantum primitives, specifically hybrid elliptic curve/post-quantum key exchange and post-quantum digital signatures, based on implementations from the Open Quantum Safe project. Among our key results, we observe that packet loss rates above 3-5% start to have a significant impact on post-quantum algorithms that fragment across many packets, such as those based on unstructured lattices. The results from this emulation framework are also complemented by results on the latency of loading entire web pages over TLS in real network conditions, which show that network latency hides most of impact from algorithms with slower computations (such as supersingular isogenies).

Keywords: post-quantum key exchange, post-quantum authentication, Transport Layer Security (TLS), network performance, emulation

Reference

Christian Paquin, Douglas Stebila, Goutam Tamvada. Benchmarking post-quantum cryptography in TLS. In Jintai Ding, Jean-Pierre Tillich, editors, Proc. 11th International Conference on Post-Quantum Cryptography (PQCrypto) 2020, LNCS, vol. 12100, pp. 72-91. Springer, April 2020. © Springer.

Download

Presentations

• 2022-06-27: European Space Agency workshop on Secure Communications for Space Missions in the Post-Quantum Era. (PDF slides)
• 2020-02-07: Netherlands Crypto Workshop. (PDF slides)
• 2019-12-17: Grenoble Alpes Cybersecurity Institute Workshop on Post-Quantum Cryptography. (PDF slides)
• 2019-12-13: IBM Research Zurich. (PDF slides)

BibTeX

@inproceedings{PQCrypto:PaqSteTam20,
 	Author = {Christian Paquin and Douglas Stebila and Goutam Tamvada},
 	Booktitle = {Proc. 11th International Conference on Post-Quantum Cryptography (PQCrypto) 2020},
 	Editor = {Jintai Ding and Jean-Pierre Tillich},
 	Month = {April},
 	Pages = {72--91},
 	Publisher = {Springer},
 	Series = {LNCS},
 	Title = {Benchmarking post-quantum cryptography in {TLS}},
 	Volume = {12100},
 	Year = {2020}
 }

Funding

• Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
• NSERC Discovery Accelerator Supplement grant RGPIN-2016-05146