More efficient post-quantum KEMTLS with pre-distributed public keys

Peter Schwabe; Douglas Stebila; Thom Wiggers

Paper 2021/779

More efficient post-quantum KEMTLS with pre-distributed public keys

Peter Schwabe

, Radboud University Nijmegen, Max Planck Institute for Security and Privacy

Douglas Stebila

, University of Waterloo

Thom Wiggers

, Radboud University Nijmegen

Abstract

While server-only authentication with certificates is the most widely used mode of operation for the Transport Layer Security (TLS) protocol on the world wide web, there are many applications where TLS is used in a different way or with different constraints. For example, embedded Internet-of-Things clients may have a server certificate pre-programmed and be highly constrained in terms of communication bandwidth or computation power. As post-quantum algorithms have a wider range of performance trade-offs, designs other than traditional ``signed-key-exchange'' may be worthwhile. The KEMTLS protocol, presented at ACM CCS 2020, uses key encapsulation mechanisms (KEMs) rather than signatures for authentication in the TLS 1.3 handshake, a benefit since most post-quantum KEMs are more efficient than PQ signatures. However, KEMTLS has some drawbacks, especially in the client authentication scenario which requires a full additional roundtrip. We explore how the situation changes with pre-distributed public keys, which may be viable in many scenarios, for example pre-installed public keys in apps, on embedded devices, cached public keys, or keys distributed out of band. Our variant of KEMTLS with pre-distributed keys, called KEMTLS-PDK, is more efficient in terms of both bandwidth and computation compared to post-quantum signed-KEM TLS (even cached public keys), and has a smaller trusted code base. When client authentication is used, KEMTLS-PDK is more bandwidth efficient than KEMTLS yet can complete client authentication in one fewer round trips, and has stronger authentication properties. Interestingly, using pre-distributed keys in KEMTLS-PDK changes the landscape on suitability of PQ algorithms: schemes where public keys are larger than ciphertexts/signatures (such as Classic McEliece and Rainbow) can be viable, and the differences between some lattice-based schemes is reduced. We also discuss how using pre-distributed public keys provides privacy benefits compared to pre-shared symmetric keys in TLS.

Note: (2022-03) Online version including proof. Corrected version that reports correct measurement of ephemeral key exchange metrics. (2024-03) Minor fixes, see changelog in paper.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Minor revision. ESORICS 2021
DOI: 10.1007/978-3-030-88418-5_1
Keywords: post-quantum cryptography TLS key exchange KEMTLS
Contact author(s): peter @ cryptojedi org
d stebila @ uwaterloo ca
thom @ thomwiggers nl
History: 2024-04-02: last of 2 revisions; 2021-06-09: received; See all versions
Short URL: https://ia.cr/2021/779
License: CC BY

BibTeX

@misc{cryptoeprint:2021/779,
      author = {Peter Schwabe and Douglas Stebila and Thom Wiggers},
      title = {More efficient post-quantum {KEMTLS} with pre-distributed public keys},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/779},
      year = {2021},
      doi = {10.1007/978-3-030-88418-5_1},
      url = {https://eprint.iacr.org/2021/779}
}