Paper 2022/065

Practical (Post-Quantum) Key Combiners from One-Wayness and Applications to TLS

Nimrod Aviram, Benjamin Dowling, Ilan Komargodski, Kenneth G. Paterson, Eyal Ronen, and Eylon Yogev


The task of combining cryptographic keys, some of which may be maliciously formed, into one key, which is (pseudo)random is a central task in cryptographic systems. For example, it is a crucial component in the widely used TLS and Signal protocols. From an analytical standpoint, current security proofs model such key combiners as dual-PRFs -- a function which is a PRF when keyed by either of its two inputs -- guaranteeing pseudo-randomness if one of the keys is compromised or even maliciously chosen by an adversary. However, in practice, protocols mostly use HKDF as a key combiner, despite the fact that HKDF was never proven to be a dual-PRF. Security proofs for these protocols usually work around this issue either by simply assuming HKDF to be a dual-PRF anyway, or by assuming ideal models (e.g. modelling underlying hash functions as random oracles). We identify several deployed protocols and upcoming standards where this is the case. Unfortunately, such heuristic approaches to security tend not to withstand the test of time, often leading to deployed systems that eventually become completely insecure. In this work, we narrow the gap between theory and practice for key combiners. In particular, we give a construction of a dual-PRF that can be used as a drop-in replacement for current heuristic key combiners in a range of protocols. Our construction follows a theoretical construction by Bellare and Lysyanskaya, and is based on concrete hardness assumptions, phrased in the spirit of one-wayness. Therefore, our construction provides security unless extremely strong attacks against the underlying cryptographic hash function are discovered. Moreover, since these assumptions are considered post-quantum secure, our construction can safely be used in new hybrid protocols. From a practical perspective, our dual-PRF construction is highly efficient, adding only a few microseconds in computation time compared to currently used (heuristic) approaches. We believe that our approach exemplifies a perfect middle-ground for practically efficient constructions that are supported by realistic hardness assumptions.

Available format(s)
Publication info
HKDFKey CombinersHybrid Key Exchange
Contact author(s)
nimrod aviram @ gmail com
b dowling @ sheffield ac uk
ilank @ cs huji ac il
kenny paterson @ inf ethz ch
eyal ronen @ cs tau ac il
eylony @ gmail com
2022-02-25: revised
2022-01-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Nimrod Aviram and Benjamin Dowling and Ilan Komargodski and Kenneth G.  Paterson and Eyal Ronen and Eylon Yogev},
      title = {Practical (Post-Quantum) Key Combiners from One-Wayness and Applications to {TLS}},
      howpublished = {Cryptology ePrint Archive, Paper 2022/065},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.