Paper 2019/134

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

Haodong Jiang, Zhenfeng Zhang, and Zhi Ma

Abstract

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.