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

Veronika Kuchta, Amin Sakzad, Damien Stehle, Ron Steinfeld, and Shi-Feng Sun

##### 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.

Note: This is the full version of the Eurocrypt 2020 paper. The differences from the Eurocrypt 2020 version are as follows: - fixed the bug in the advantage of the optimal distinguisher discussed in the Introduction (Adv(A) = sqrt((2-p_x)*px) vs. Adv(A)=sqrt(p_x) in the conference version). - added two appendices: Appendix A for missing std definitions, and Appendix B for security loss computation details of Table 2.

Available format(s)
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.EUROCRYPT 2020
Keywords
QROMsecurity proofpublic-key encryption
Contact author(s)
ron steinfeld @ monash edu
History
Short URL
https://ia.cr/2021/454

CC BY

BibTeX

@misc{cryptoeprint:2021/454,
author = {Veronika Kuchta and Amin Sakzad and Damien Stehle and Ron Steinfeld and Shi-Feng Sun},
title = {Measure-Rewind-Measure: Tighter Quantum Random Oracle Model Proofs for One-Way to Hiding and CCA Security},
howpublished = {Cryptology ePrint Archive, Paper 2021/454},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/454}},
url = {https://eprint.iacr.org/2021/454}
}
`
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.