Paper 2018/884

Key Encapsulation from Noisy Key Agreement in the Quantum Random Oracle Model

Alan Szepieniec, Reza Reyhanitabar, and Bart Preneel


A multitude of post-quantum key encapsulation mechanisms (KEMs) and public key encryption (PKE) schemes implicitly rely on a protocol by which Alice and Bob exchange public messages and converge on secret values that are identical up to some small noise. By our count, 24 out of 49 KEM or PKE submissions to the NIST Post-Quantum Cryptography Standardization project follow this strategy. Yet the notion of a noisy key agreement (NKA) protocol lacks a formal definition as a primitive in its own right. We provide such a formalization by defining the syntax and security for an NKA protocol. This formalization brings out four generic problems, called A and B State Recovery, Noisy Key Search and Noisy Key Distinguishing, whose solutions must be hard in the quantum computing model. Informally speaking, these can be viewed as noisy, quantum-resistant counterparts of the problems arising from the classical Diffie-Hellman type protocols. We show that many existing proposals contain an NKA component that fits our formalization and we reveal the induced concrete hardness assumptions. The question arises whether considering NKA as an independent primitive can help provide modular designs with improved efficiency and/or proofs. As the second contribution of this paper, we answer this question positively by presenting a generic transform from a secure NKA protocol to an IND-CCA secure KEM in the quantum random oracle model, with a security bound tightly related to the NKD problem. This transformation is essentially the same as that of the NIST candidate Ramstake. While establishing the security of Ramstake was our initial objective, the collection of tools that came about as a result of this journey is of independent interest.

Available format(s)
Public-key cryptography
Publication info
key exchangekey encapsulation mechanismpost-quantum cryptographyquantum random oracle model
Contact author(s)
alan szepieniec @ esat kuleuven be
2019-04-02: last of 7 revisions
2018-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alan Szepieniec and Reza Reyhanitabar and Bart Preneel},
      title = {Key Encapsulation from Noisy Key Agreement in the Quantum Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2018/884},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.