Measure-Rewind-Measure: tighter quantum random oracle model proofs for one-way to hiding and CCA security

Veronika Kuchta, Amin Sakzad, Damien Stehlé, Ron Steinfeld, Shi Feng Sun

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

5 Citations (Scopus)


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 (IND-CCA) Key Encapsulation Mechanism (KEM) from a weak (IND-CPA) public-key encryption scheme satisfying a mild injectivity assumption.

Original languageEnglish
Title of host publicationAdvances in Cryptology – EUROCRYPT 2020
Subtitle of host publication39th Annual International Conference on the Theory and Applications of Cryptographic Techniques Zagreb, Croatia, May 10–14, 2020 Proceedings, Part III
EditorsAnne Canteaut, Yuval Ishai
Number of pages26
EditionCham Switzerland
ISBN (Electronic)9783030457273
ISBN (Print)9783030457266
Publication statusPublished - 2020
EventInternational Conference on the Theory and Application of Cryptographic Techniques 2020 - Online
Duration: 11 May 202015 May 2020
Conference number: 39th (Proceedings) (Website)

Publication series

NameLecture Notes in Computer Science
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


ConferenceInternational Conference on the Theory and Application of Cryptographic Techniques 2020
Abbreviated titleEUROCRYPT 2020
Internet address


  • Public-key encryption
  • QROM
  • Security proof

Cite this