Welcome to the resource topic for 2023/862
Title:
Tighter QCCA-Secure Key Encapsulation Mechanism with Explicit Rejection in the Quantum Random Oracle Model
Authors: Jiangxia Ge, Tianshu Shan, Rui Xue
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 Ho"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.
ePrint: https://eprint.iacr.org/2023/862
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .