Paper 2017/1005

Tightly-Secure Key-Encapsulation Mechanism in the Quantum Random Oracle Model

Tsunekazu Saito and Keita Xagawa and Takashi Yamakawa

Abstract

We give a tighter security reduction for a conversion from a weakly-secure public-key encryption scheme to an IND-CCA-secure key-encapsulation mechanism scheme in the quantum random oracle model. To the best of our knowledge, previous reductions are non-tight as the security levels of the obtained schemes are degraded to at most \emph{half, quarter, or an eighth} of the original security level (Boneh, Dagdelen, Fischlin, Lehmann, Schafner, and Zhandry (CRYPTO 2012), Targhi and Unruh (TCC 2016-B), and Hofheinz, Hövelmanns, and Kiltz (TCC 2017)).

Note: Please see the version notes in Section 1.5. For example, we replace PR-CPA with Disjoint Simulatability, replace THalf with TPunc, and add concrete instantiations.