Paper 2023/862

Tighter QCCA-Secure Key Encapsulation Mechanism with Explicit Rejection in the Quantum Random Oracle Model

Jiangxia Ge, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Tianshu Shan, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Rui Xue, State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100093, China, School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Abstract

Hofheinz et al. (TCC 2017) proposed several key encapsulation mechanism (KEM) variants of Fujisaki-Okamoto (\textsf{FO}) transformation, including $\textsf{FO}^{\slashed{\bot}}$, $\textsf{FO}_m^{\slashed{\bot}}$, $\textsf{QFO}_m^{\slashed{\bot}}$, $\textsf{FO}^{\bot}$, $\textsf{FO}_m^\bot$ and $\textsf{QFO}_m^\bot$, and they are widely used in the post-quantum cryptography standardization launched by NIST. These transformations are divided into two types, the implicit and explicit rejection type, including $\{\textsf{FO}^{\slashed{\bot}}, \textsf{FO}_m^{\slashed{\bot}}, \textsf{QFO}_m^{\slashed{\bot}}\}$ and $\textsf{FO}^{\bot}, \textsf{FO}_m^\bot, \textsf{QFO}_m^\bot$, respectively. The decapsulation algorithm of the implicit (resp. explicit) rejection type returns a pseudorandom value (resp. an abort symbol $\bot$) for an invalid ciphertext. For the implicit rejection type, the \textsf{IND-CCA} security reduction of $\textsf{FO}^{\slashed{\bot}}$ in the quantum random oracle model (QROM) can avoid the quadratic security loss, as shown by Kuchta et al. (EUROCRYPT 2020). However, for the explicit rejection type, the best known \textsf{IND-CCA} security reduction in the QROM presented by Hövelmanns et al. (ASIACRYPT 2022) for $\textsf{FO}_m^\bot$ still suffers from a quadratic security loss. Moreover, it is not clear until now whether the implicit rejection type is more secure than the explicit rejection type. In this paper, a QROM security reduction of $\textsf{FO}_m^\bot$ without incurring a quadratic security loss is provided. Furthermore, our reduction achieves \textsf{IND-qCCA} security, which is stronger than the \textsf{IND-CCA} security. To achieve our result, two steps are taken: The first step is to prove that the \textsf{IND-qCCA} security of $\textsf{FO}_m^\bot$ can be tightly reduced to the \textsf{IND-CPA} security of $\textsf{FO}_m^\bot$ by using the online extraction technique proposed by Don et al. (EUROCRYPT 2022). The second step is to prove that the \textsf{IND-CPA} security of $\textsf{FO}_m^\bot$ can be reduced to the \textsf{IND-CPA} security of the underlying public key encryption (PKE) scheme without incurring quadratic security loss by using the Measure-Rewind-Measure One-Way to Hiding Lemma (EUROCRYPT 2020). In addition, we prove that (at least from a theoretic point of view), security is independent of whether the rejection type is explicit ($\textsf{FO}_m^\bot$) or implicit ($\textsf{FO}_m^{\slashed{\bot}}$) if the underlying PKE scheme is weakly $\gamma$-spread.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2023
Keywords
Fujisaki-Okamoto transformationquantum random oraclekey encapsulation mechanismquantum chosen-ciphertext attack
Contact author(s)
gejiangxia @ iie ac cn
shantianshu @ iie ac cn
xuerui @ iie ac cn
History
2023-06-07: revised
2023-06-07: received
See all versions
Short URL
https://ia.cr/2023/862
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/862,
      author = {Jiangxia Ge and Tianshu Shan and Rui Xue},
      title = {Tighter {QCCA}-Secure Key Encapsulation Mechanism with Explicit Rejection in the Quantum Random Oracle Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/862},
      year = {2023},
      url = {https://eprint.iacr.org/2023/862}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.