Paper 2020/099

Many a Mickle Makes a Muckle: A Framework for Provably Quantum-Secure Hybrid Key Exchange

Benjamin Dowling, Torben Brandt Hansen, and Kenneth G. Paterson


Hybrid Authenticated Key Exchange (AKE) protocols combine keying material from different sources (post-quantum, classical, and quantum key distribution (QKD)) to build protocols that are resilient to catastrophic failures of the different components. These failures may be due to advances in quantum computing, implementation vulnerabilities, or our evolving understanding of the quantum (and even classical) security of supposedly quantum-secure primitives. This hybrid approach is a prime candidate for initial deployment of post-quantum-secure cryptographic primitives because it hedges against undiscovered weaknesses. We propose a general framework HAKE for analysing the security of such hybrid AKE protocols. HAKE extends the classical Bellare-Rogaway model for AKE security to encompass forward security, post-compromise security, fine-grained compromise of different cryptographic components, and more. We use the framework to provide a security analysis of a new hybrid AKE protocol named Muckle. This protocol operates in one round trip and leverages the pre-established symmetric keys that are inherent to current QKD designs to provide message authentication, avoiding the need to use expensive post-quantum signature schemes. We provide an implementation of our Muckle protocol, instantiating our generic construction with classical and post-quantum Diffie-Hellman-based algorithmic choices. Finally, we report on benchmarking exercises against our implementation, examining its performance in terms of clock cycles, elapsed wall-time, and additional latency in both LAN and WAN settings.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.PQCrypto 2020
Authenticated key exchangehybrid key exchangeprovable securityprotocol analysisquantum key distributionpost-compromise security
Contact author(s)
dowling bj @ gmail com
2020-02-04: received
Short URL
Creative Commons Attribution


      author = {Benjamin Dowling and Torben Brandt Hansen and Kenneth G.  Paterson},
      title = {Many a Mickle Makes a Muckle: A Framework for Provably Quantum-Secure Hybrid Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2020/099},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.