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

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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ESORICS 2021
post-quantum cryptographyTLSkey exchangeKEMTLS
Contact author(s)
peter @ cryptojedi org
d stebila @ uwaterloo ca
thom @ thomwiggers nl
2024-04-02: last of 2 revisions
2021-06-09: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.