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 tran...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHANG, Zhengyu, WEI, Puwen, XUE, Haiyang
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2019
Subjects:
KEM
CCA
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
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary: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.