Transitioning to a quantum-resistant public key infrastructure

Compatibility of TLS connections using hybrid X.509v3 certificates containing large extensions.


To ensure uninterrupted cryptographic security, it is important to begin planning the transition to post-quantum cryptography. In addition to creating post-quantum primitives, we must also plan how to adapt the cryptographic infrastructure for the transition, especially in scenarios such as public key infrastructures (PKIs) with many participants. The use of hybrids—multiple algorithms in parallel—will likely play a role during the transition for two reasons: “hedging our bets” when the security of newer primitives is not yet certain but the security of older primitives is already in question; and to achieve security and functionality both in post-quantum-aware and in a backwards-compatible way with not-yet-upgraded software.

In this paper, we investigate the use of hybrid digital signature schemes. We consider several methods for combining signature schemes, and give conditions on when the resulting hybrid signature scheme is unforgeable. Additionally we address a new notion about the inability of an adversary to separate a hybrid signature into its components. For both unforgeability and non-separability, we give a novel security hierarchy based on how quantum the attack is. We then turn to three real-world standards involving digital signatures and PKI: certificates (X.509), secure channels (TLS), and email (S/MIME). We identify possible approaches to supporting hybrid signatures in these standards while retaining backwards compatibility, which we test in popular cryptographic libraries and implementations, noting especially the inability of some software to handle larger certificates.

Keywords: post-quantum cryptography, public key infrastructure, digital signatures


Nina Bindel, Udyani Herath, Matthew McKague, Douglas Stebila. Transitioning to a quantum-resistant public key infrastructure. In Tanja Lange, Tsuyoshi Takagi, editors, Proc. 8th International Conference on Post-Quantum Cryptography (PQCrypto) 2017, LNCS, vol. 10346, pp. 384-405. Springer, June 2017. © Springer.



  • Scripts for generating and testing hybrid certificates for post-quantum PKI: Download ZIP file



This research was supported by:
  • Natural Sciences and Engineering Research Council of Canada (NSERC) Discovery grant RGPIN-2016-05146
  • NSERC Discovery Accelerator Supplement grant RGPIN-2016-05146
  • German Research Foundation (DFG) as part of project P1 within the CRC 1119 CROSSING