QCCA-Secure Generic Key Encapsulation Mechanism with Tighter Security in the Quantum Random Oracle Model

Xagawa and Yamakawa (PQCrypto 2019) proved the transformation \(\mathsf {SXY}\) can tightly turn \(\mathsf {DS}\) secure \(\mathsf {PKE}\)s into \(\mathsf {IND}\text {-}\mathsf{qCCA}\) secure \(\mathsf {KEM}\)s in the quantum random oracle model (QROM). But transformations such as \(\mathsf {KC,\ TPunc}\) that turn PKEs with standard security (\(\mathsf {OW}\text {-}\mathsf{CPA}\) or \(\mathsf {IND}\text {-}\mathsf{CPA}\)) into \(\mathsf {DS}\) secure \(\mathsf {PKE}\)s still suffer from quadratic security loss in the QROM. In this paper, we give a tighter security reduction for the transformation \(\mathsf {KC}\) that turns \(\mathsf {OW}\text {-}\mathsf{CPA}\) secure deterministic \(\mathsf {PKE}\)s into modified \(\mathsf {DS}\) secure \(\mathsf {PKE}\)s in the QROM. We use the Measure-Rewind-Measure One-Way to Hiding Lemma recently introduced by Kuchta et al. (EUROCRYPT 2020) to avoid the square-root advantage loss. Moreover, we extend it to the case that underlying \(\mathsf {PKE}\)s are not perfectly correct. Combining with other transformations, we finally obtain a generic \(\mathsf {KEM}\) from any \(\mathsf {IND}\text {-}\mathsf{CPA}\) secure \(\mathsf {PKE}\). Our security reduction has roughly the same tightness as the result of Kuchta et al. without any other assumptions and we achieve the stronger \(\mathsf {IND}\text {-}\mathsf{qCCA}\) security. We also give a similar result for another \(\mathsf {KEM}\) transformation achieving the same security notion from any \(\mathsf {OW}\text {-}\mathsf{CPA}\) secure deterministic \(\mathsf {PKE}\).