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

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

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 (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
PublisherSpringer
Pages703-728
Number of pages26
EditionCham Switzerland
ISBN (Electronic)9783030457273
ISBN (Print)9783030457266
DOIs
Publication statusPublished - 2020
EventInternational Conference on the Theory and Application of Cryptographic Techniques 2020 - Online
Duration: 11 May 202015 May 2020
Conference number: 39th
https://link-springer-com.ezproxy.lib.monash.edu.au/book/10.1007/978-3-030-45727-3 (Proceedings)
https://eurocrypt.iacr.org/2020/ (Website)

Publication series

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

Conference

ConferenceInternational Conference on the Theory and Application of Cryptographic Techniques 2020
Abbreviated titleEUROCRYPT 2020
Period11/05/2015/05/20
Internet address

Keywords

  • Public-key encryption
  • QROM
  • Security proof

Cite this

Kuchta, V., Sakzad, A., Stehlé, D., Steinfeld, R., & Sun, S. F. (2020). Measure-Rewind-Measure: tighter quantum random oracle model proofs for one-way to hiding and CCA security. In A. Canteaut, & Y. Ishai (Eds.), Advances in Cryptology – EUROCRYPT 2020 : 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques Zagreb, Croatia, May 10–14, 2020 Proceedings, Part III (Cham Switzerland ed., pp. 703-728). (Lecture Notes in Computer Science ; Vol. LNCS). Springer. https://doi.org/10.1007/978-3-030-45727-3_24