International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Measure-Rewind-Extract: Tighter Proofs of One-Way to Hiding and CCA Security in the Quantum Random Oracle Model

Authors:
Jiangxia Ge , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100084, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Heming Liao , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100084, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Rui Xue , Key Laboratory of Cyberspace Security Defense, Institute of Information Engineering, Chinese Academy of Sciences, Beijing 100084, China; School of Cyber Security, University of Chinese Academy of Sciences, Beijing 100049, China
Download:
Search ePrint
Search Google
Conference: ASIACRYPT 2024
Abstract: The One-Way to Hiding (O2H) theorem, first given by Unruh (J ACM 2015) and then restated by Ambainis et al. (CRYPTO 2019), is a crucial technique for solving the reprogramming problem in the quantum random oracle model (QROM). It provides an upper bound d\cdot\sqrt{\epsilon} for the distinguisher's advantage, where d is the query depth and \epsilon denotes the advantage of a one-wayness attacker. Later, in order to obtain a tighter upper bound, Kuchta et al. (EUROCRYPT 2020) proposed the Measure-Rewind-Measure (MRM) technique and then proved the Measure-Rewind-Measure O2H (MRM-O2H) theorem, which provides the upper bound d\cdot\epsilon. They also proposed an open question: Can we combine their MRM technique with Ambainis et al.'s semi-classical oracle technique (CRYPTO 2019) or Zhandry's compressed oracle technique (CRYPTO 2019) to prove a new O2H theorem with an upper bound even tighter than d\cdot\epsilon? In this paper, we give an affirmative answer for the above question. We propose a new technique named Measure-Rewind-Extract (MRE) by combining the MRM technique with the semi-classical oracle technique. By using MRE technique, we prove the Measure-Rewind-Extract O2H (MRE-O2H) theorem, which provides the upper bound \sqrt{d}\cdot\epsilon. As an important application of our MRE-O2H theorem, for the FO^{\slashed{\bot}}, FO_m^\slashed{\bot}, FO^{\bot} and FO_m^\bot proposed by Hofheinz et al. (TCC 2017), i.e., the key encapsulation mechanism (KEM) variants of the Fujisaki-Okamoto transformation, we prove the following results in the QROM: Their IND-CCA security can be reduced to the IND-CPA security of the underlying public key encryption (PKE) scheme without the square-root advantage loss. In particular, compared with the IND-CCA proof of FO^{\slashed{\bot}} given by Kuchta et al. (EUROCRYPT 2020), ours removes the injectivity assumption and has a tighter security bound. Under the assumption that the underlying PKE scheme is unique randomness recoverable, we for the first time prove that their IND-CCA security can be reduced to the OW-CPA security of the underlying PKE scheme without the square-root advantage loss.
BibTeX
@inproceedings{asiacrypt-2024-34573,
  title={Measure-Rewind-Extract: Tighter Proofs of One-Way to Hiding and CCA Security in the Quantum Random Oracle Model},
  publisher={Springer-Verlag},
  author={Jiangxia Ge and Heming Liao and Rui Xue},
  year=2024
}