Paper 2019/134

Tighter security proofs for generic key encapsulation mechanism in the quantum random oracle model

Haodong Jiang, Zhenfeng Zhang, and Zhi Ma


In (TCC 2017), Hofheinz, Hoevelmanns and Kiltz provided a fine-grained and modular toolkit of generic key encapsulation mechanism (KEM) constructions, which were widely used among KEM submissions to NIST Post-Quantum Cryptography Standardization project. The security of these generic constructions in the quantum random oracle model (QROM) has been analyzed by Hofheinz, Hoevelmanns and Kiltz (TCC 2017), Saito, Xagawa and Yamakawa (Eurocrypt 2018), and Jiang et al. (Crypto 2018). However, the security proofs from standard assumptions are far from tight. In particular, the factor of security loss is $q$ and the degree of security loss is 2, where $q$ is the total number of adversarial queries to various oracles. In this paper, using semi-classical oracle technique recently introduced by Ambainis, Hamburg and Unruh (ePrint 2018/904), we improve the results in (Eurocrypt 2018, Crypto 2018) and provide tighter security proofs for generic KEM constructions from standard assumptions. More precisely, the factor of security loss $q$ is reduced to be $\sqrt{q}$. In addition, for transformation T that turns a probabilistic public-key encryption (PKE) into a determined one by derandomization and re-encryption, the degree of security loss 2 is reduced to be 1. Our tighter security proofs can give more confidence to NIST KEM submissions where these generic transformations are used, e.g., CRYSTALS-Kyber etc.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
quantum random oracle modelkey encapsulation mechanismgeneric construction
Contact author(s)
hdjiang13 @ gmail com
2019-02-14: revised
2019-02-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Haodong Jiang and Zhenfeng Zhang and Zhi Ma},
      title = {Tighter security proofs for generic key encapsulation mechanism in the quantum random oracle model},
      howpublished = {Cryptology ePrint Archive, Paper 2019/134},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.