Paper 2022/1556

Intermediate Certificate Suppression in Post-Quantum TLS: An Approximate Membership Querying Approach

Dimitrios Sikeridis, VMware xLabs
Sean Huntley, VMware xLabs
David Ott, VMware Research
Michael Devetsikiotis, University of New Mexico

Quantum computing advances threaten the security of today's public key infrastructure, and have led to the pending standardization of alternative, quantum-resistant key encapsulation and digital signature cryptography schemes. Unfortunately, authentication algorithms based on the new post-quantum (PQ) cryptography create significant performance bottlenecks for TLS due to larger certificate chains which introduce additional packets and round-trips. The TLS handshake slowdown will be unacceptable to many applications, and detrimental to the broader adoption of quantum safe cryptography standards. In this paper, we propose a novel framework for Intermediate Certificate Authority (ICA) certificate suppression in TLS that reduces the authentication message size and prevents excessive round-trip delays. Our approach utilizes an approximate membership query (AMQ) data structure (probabilistic filter) to advertise known ICA certs to remote TLS endpoints so that unnecessary ICA certificates are omitted from the TLS handshake exchange. We showcase the extend of the PQ authentication overhead challenge in TLS, and evaluate the feasibility of AMQ filters for ICA suppression in terms of space and computational overhead. Finally, we experimentally evaluate the potential gains form our approach and showcase a $70\%$ reduction in exchanged ICA cert data that translates to 15-50 MB of savings in PQ TLS and for certain Web-based application scenarios.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. 18th International Conference on emerging Networking EXperiments and Technologies (CoNEXT '22)
Post-Quantum CryptographyPost-Quantum TLSIntermediate CertificatesApproximate Membership Querying
Contact author(s)
sikeridisd @ vmware com
shuntley @ vmware com
dott @ vmware com
mdevets @ unm edu
2023-12-08: revised
2022-11-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dimitrios Sikeridis and Sean Huntley and David Ott and Michael Devetsikiotis},
      title = {Intermediate Certificate Suppression in Post-Quantum TLS: An Approximate Membership Querying Approach},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1556},
      year = {2022},
      doi = {10.1145/3555050.3569127},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.