Paper 2019/494

On the non-tightness of measurement-based reductions for key encapsulation mechanism in the quantum random oracle model

Haodong Jiang and Zhenfeng Zhang and Zhi Ma

Abstract

Key encapsulation mechanism (KEM) variants of the Fujisaki-Okamoto (FO) transformation (CRYPTO 1999 and Journal of Cryptology 2013) that turn a weakly-secure public-key encryption (PKE) into an IND-CCA-secure KEM, were proposed by Hofheinz, Hoevelmanns and Kiltz (TCC 2017) and widely used among the KEM submissions to the NIST Post-Quantum Cryptography Standardization Project. The security reductions for these variants in the quantum random oracle model (QROM) were given by Hofheinz, Hoevelmanns and Kiltz (TCC 2017) and Jiang et al. (Crypto 2018). However, under standard CPA security assumptions, i.e., OW-CPA and IND-CPA, all these security reductions are far from desirable due to the quadratic security loss. In this paper, for KEM variants of the FO transformation, we show that a typical measurement-based reduction in the QROM from breaking standard OW-CPA (or IND-CPA) security of the underlying PKE to breaking the IND-CCA security of the resulting KEM, will inevitably incur a quadratic loss of the security, where ``measurement-based" means the reduction measures a hash query from the adversary and uses the measurement outcome to break the underlying security of PKE. In particular, all currently known security reductions in (TCC 2017 and Crypto 2018) are of this type, and our results suggest an explanation for the lack of progress in improving the reduction tightness in terms of the degree of security loss. We emphasize that our results do not expose any post-quantum security weakness of KEM variants of FO transformation.