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

Tsunekazu Saito; Keita Xagawa; Takashi Yamakawa

Paper 2017/1005

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

Tsunekazu Saito, Keita Xagawa, and Takashi Yamakawa

Abstract

Key-encapsulation mechanisms secure against chosen ciphertext attacks (IND-CCA-secure KEMs) in the quantum random oracle model have been proposed by Boneh, Dagdelen, Fischlin, Lehmann, Schafner, and Zhandry (CRYPTO 2012), Targhi and Unruh (TCC 2016-B), and Hofheinz, Hövelmanns, and Kiltz (TCC 2017). However, all are non-tight and, in particular, security levels of the schemes obtained by these constructions are less than half of original security levels of their building blocks. In this paper, we give a conversion that tightly converts a weakly secure public-key encryption scheme into an IND-CCA-secure KEM in the quantum random oracle model. More precisely, we define a new security notion for deterministic public key encryption (DPKE) called the disjoint simulatability, and we propose a way to convert a disjoint simulatable DPKE scheme into an IND-CCA-secure key-encapsulation mechanism scheme without incurring a significant security degradation. In addition, we give DPKE schemes whose disjoint simulatability is tightly reduced to post-quantum assumptions. As a result, we obtain IND-CCA-secure KEMs tightly reduced to various post-quantum assumptions in the quantum random oracle model.

Note: * add a new conversion KC that converts a perfectly-correct OW-CPA-secure DPKE scheme into a perfectly-correct disjoint-simulatable DPKE scheme with a quadratic loss in the QROM. In the ROM, the security proof is tight. * update implementation results of NTRU-HRSS-SXY with AVX2. * 2021: Correct lemmas and adjust constants.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A major revision of an IACR publication in EUROCRYPT 2018
Keywords: Tight security chosen-ciphertext security post-quantum cryptography KEM
Contact author(s): keita xagawa zv @ hco ntt co jp
History: 2021-08-25: last of 6 revisions; 2017-10-13: received; See all versions
Short URL: https://ia.cr/2017/1005
License: CC BY

BibTeX

@misc{cryptoeprint:2017/1005,
      author = {Tsunekazu Saito and Keita Xagawa and Takashi Yamakawa},
      title = {Tightly-Secure Key-Encapsulation Mechanism in the Quantum Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1005},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/1005}},
      url = {https://eprint.iacr.org/2017/1005}
}