Tighter Security Proofs for Post-quantum Key Encapsulation Mechanism in the Multi-challenge Setting

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 \(\delta \)-correctness) using Open image in new window 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.