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

Hofheinz et al. (TCC 2017) proposed several key encapsulation mechanism (KEM) variants of Fujisaki-Okamoto (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 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 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 IND-qCCA security, which is stronger than the IND-CCA security. To achieve our result, two steps are taken: The first step is to prove that the IND-qCCA security of $\textsf{FO}_m^\bot$ can be tightly reduced to the 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 IND-CPA security of $\textsf{FO}_m^\bot$ can be reduced to the 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.