Tighter security proofs for post-quantum key encapsulation mechanism in the multi-challenge setting

• Main Authors: ZHANG, Zhengyu, WEI, Puwen, XUE, Haiyang
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2019
• Subjects: KEM; QROM; CCA; Tight security; Information Security
• Online Access: https://ink.library.smu.edu.sg/sis_research/9204; https://ink.library.smu.edu.sg/context/sis_research/article/10209/viewcontent/tighter.pdf
• Institution: Singapore Management University

Due to the threat posed by quantum computers, a series of works investigate the security of cryptographic schemes in the quantum-accessible random oracle model (QROM) where the adversary can query the random oracle in superposition. In this paper, we present tighter security proofs of a generic transformations for key encapsulation mechanism (KEM) in the QROM in the multi-challenge setting, where the reduction loss is independent of the number of challenge ciphertexts. In particular, we introduce the notion of multi-challenge OW-CPA (mOW-CPA) security, which captures the one-wayness of the underlying public key encryption (PKE) under chosen plaintext attack in the multi-challenge setting. We show that the multi-challenge IND-CCA (mIND-CCA) security of KEM can be reduced to the mOW-CPA security of the underlying PKE scheme (with �-correctness) using transformation. Then we prove that the mOW-CPA security can be tightly reduced to the underlying post-quantum assumptions by showing the tight mOW-CPA security of two concrete PKE schemes based on LWE, where one is the Regev’s PKE scheme and the other is a variant of Frodo.