International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Tianshu Shan

ORCID: 0000-0002-1918-7464

Publications

Year
Venue
Title
2023
PKC
QCCA-Secure Generic Transformations in the Quantum Random Oracle Model
Tianshu Shan Jiangxia Ge Rui Xue
The post-quantum security of cryptographic schemes assumes that the quantum adversary only receives the classical result of computations with the secret key. Further, it is unknown whether the post-quantum secure schemes still remain secure if the adversary can obtain a superposition state of the results. In this paper, we formalize one class of public-key encryption schemes named oracle-masked schemes. Then we define the plaintext extraction procedure for those schemes and this procedure simulates the quantum-accessible decryption oracle with a certain loss. The construction of the plaintext extraction procedure does not need to take the secret key as input. Based on this property, we prove the IND-qCCA security of the Fujisaki-Okamoto (FO) transformation in the quantum random oracle model (QROM) and our security proof is tighter than the proof given by Zhandry (Crypto 2019). We also give the first IND-qCCA security proof of the REACT transformation in the QROM. Furthermore, our formalization can be applied to prove the IND-qCCA security of key encapsulation mechanisms with explicit rejection. As an example, we present the IND-qCCA security proof of TCH transformation, proposed by Huguenin-Dumittan and Vaudenay (Eurocrypt 2022), in the QROM.
2023
CRYPTO
Tighter QCCA-Secure Key Encapsulation Mechanism with Explicit Rejection in the Quantum Random Oracle Model
Jiangxia Ge Tianshu Shan Rui Xue
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{\"o}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.

Coauthors

Jiangxia Ge (2)
Rui Xue (2)