Hybrid key encapsulation mechanisms and authenticated key exchange

KEM constructed by the dual PRF combiner compared to key schedule from proposed hybrid key exchange draft for TLS 1.3


Concerns about the impact of quantum computers on currently deployed public key cryptography have instigated research into not only quantum-resistant cryptographic primitives but also how to transition applications from classical to quantum-resistant solutions. One approach to mitigate the risk of quantum attacks and to preserve common security guarantees are hybrid schemes, which combine classically secure and quantum-resistant schemes. Various academic and industry experiments and draft standards related to the Transport Layer Security (TLS) protocol already use some form of hybrid key exchange; however sound theoretical approaches to substantiate the design and security of such hybrid key exchange protocols are missing so far.

We initiate the modeling of hybrid authenticated key exchange protocols. We consider security against adversaries with varying levels of quantum power over time, such as adversaries who may become quantum in the future or are quantum in the present. We reach our goal using a three-step approach: First, we introduce security notions for key encapsulation mechanisms (KEMs) that enable a fine-grained distinction between different quantum scenarios. Second, we propose several combiners for constructing hybrid KEMs that correspond closely to recently proposed Internet-Drafts for hybrid key exchange in TLS 1.3. Finally, we present a provably sound design for hybrid key exchange using KEMs as building blocks.

Keywords: hybrid key exchange, key exchange, hybrids, combiners, post-quantum key exchange


Nina Bindel, Jacqueline Brendel, Marc Fischlin, Brian Goncalves, Douglas Stebila. Hybrid key encapsulation mechanisms and authenticated key exchange. In Jintai Ding, Rainer Steinwandt, editors, Proc. 10th International Conference on Post-Quantum Cryptography (PQCrypto) 2019, LNCS, vol. 11505, pp. 206--226. Springer, May 2019. © Springer.




This research was supported by:
  • Natural Sciences and Engineering Research Council (NSERC) of Canada Discovery grant RGPIN-2016-05146
  • Heisenberg grant Fi 940/3-2 of the German Research Foundation (DFG) as part of project S4 within the CRC~1119 CROSSING