International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Measure-Rewind-Measure: Tighter Quantum Random Oracle Model Proofs for One-Way to Hiding and CCA Security

Authors:
Veronika Kuchta , Monash University
Amin Sakzad , Monash University
Damien Stehlé , Univ. Lyon, EnsL, UCBL, CNRS, Inria, LIP, Institut Universitaire de France
Ron Steinfeld , Monash University
Shi-Feng Sun , Monash University, Data61, CSIRO
Download:
DOI: 10.1007/978-3-030-45727-3_24 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: We introduce a new technique called `Measure-Rewind-Measure' (MRM) to achieve tighter security proofs in the quantum random oracle model (QROM). We first apply our MRM technique to derive a new security proof for a variant of the `double-sided' quantum One-Way to Hiding Lemma (O2H) of Bindel et al. [TCC 2019] which, for the first time, avoids the square-root advantage loss in the security proof. In particular, it bypasses a previous `impossibility result' of Jiang, Zhang and Ma [IACR eprint 2019]. We then apply our new O2H Lemma to give a new tighter security proof for the Fujisaki-Okamoto transform for constructing a strong (INDCCA) Key Encapsulation Mechanism (KEM) from a weak (INDCPA) public-key encryption scheme satisfying a mild injectivity assumption.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30231,
  title={Measure-Rewind-Measure: Tighter Quantum Random Oracle Model Proofs for One-Way to Hiding and CCA Security},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={QROM;security proof;public-key encryption.},
  volume={12105},
  doi={10.1007/978-3-030-45727-3_24},
  author={Veronika Kuchta and Amin Sakzad and Damien Stehlé and Ron Steinfeld and Shi-Feng Sun},
  year=2020
}