Tighter Security Proofs For Post-quantum Key Encapsulation Mechanism In The Multi-challenge Setting

Due to the rapid advance in quantum computing,which would seriously com-promise the security of public key cryptosystems currently in use?post-quantum cryptography has attracted wide attention and many countries have initiated projects for the design of post-quantum cryptographic schemes since 2016.How-ever,many post-quantum cryptographic schemes are proven secure in the classic random oracle model,where some properties of the random oracle may not hold in the quantum setting.Hence,researchers began to consider the quantum ran-dom oracle model(QROM),where the adversary can query the random oracle in superposition.In addition,the standard security notions for encryptions only consider one challenge ciphertext,while the realistic setting usually involves more ciphertexts,which is closely related the concrete security of encryptions.There-fore,it is important to consider the post-quantum security of encryptions in the multi-challenge ciphertext setting.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 FOtransformation.Then we prove that the mOW-CPA security can be tightly reduced to the underlying post-quantum assumpt.ions 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.By applying the generic transformations FO to those schemes in the QROM,we can construct KEM with tighter multi-challenge IND-CCA security,where the security loss is independent on the number of the challenge chipertexts.