Lune

EUROCRYPT2021Top-tier venue

Classical vs Quantum Random Oracles

Takashi Yamakawa, Mark Zhandry

Abstract

In this paper, we study relationship between security of cryptographic schemes in the random oracle model (ROM) and quantum random oracle model (QROM). First, we introduce a notion of a proof of quantum access to a random oracle (PoQRO), which is a protocol to prove the capability to quantumly access a random oracle to a classical verifier. We observe that a proof of quantumness recently proposed by Brakerski et al. (TQC '20) can be seen as a PoQRO. We also give a construction of a publicly verifiable PoQRO relative to a classical oracle. Based on them, we construct digital signature and public key encryption schemes that are secure in the ROM but insecure in the QROM. In particular, we obtain the first examples of natural cryptographic schemes that separate the ROM and QROM under a standard cryptographic assumption.

On the other hand, we give lifting theorems from security in the ROM to that in the QROM for certain types of cryptographic schemes and security notions. For example, our lifting theorems are applicable to Fiat-Shamir non-interactive arguments, Fiat-Shamir signatures, and Full-Domain-Hash signatures etc. We also discuss applications of our lifting theorems to quantum query complexity.

Ask Lune

Know this paper in minutes, not an afternoon.

Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.

9 top-tier papers have cited it since. Know what they found before your reviewers do.

Questions to start from

Lune can draw on

the full paper · the top-tier papers that cite it · related work

Get the answer

Free to start. No credit card required.

Lineage

  • Verifiable Quantum Advantage without Structure cites One-shot signatures and applications to hybrid quantum/classical authentication
  • Constructive Post-Quantum Reductions cites The Measure-and-Reprogram Technique 2.0: Multi-round Fiat-Shamir and More
  • Candidate Obfuscation via Oblivious LWE Sampling cites Indistinguishability obfuscation from circular security
  • Candidate Obfuscation via Oblivious LWE Sampling cites Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FE
Builds onCited byLeft to right by year; the more cited, the higher.

Cited by top-tier papers9

  1. Verifiable Quantum Advantage without StructureTakashi Yamakawa, Mark ZhandryFOCS 2022 · 35 citations
  2. Squirrel: Efficient Synchronized Multi-Signatures from LatticesNils Fleischhacker, Mark Simkin, Zhenfei ZhangCCS 2022 · 33 citations
  3. Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way FunctionsFuyuki Kitagawa, Tomoyuki Morimae, Ryo Nishimaki, Takashi YamakawaCRYPTO 2024 · 13 citations
  4. Constructive Post-Quantum ReductionsNir Bitansky, Zvika Brakerski, Yael Tauman KalaiCRYPTO 2022 · 13 citations
  5. Compressed Permutation OraclesJoseph CarolanSTOC 2026 · 13 citations

Builds on5

  1. Indistinguishability obfuscation from circular securityRomain Gay, Rafael PassSTOC 2021 · 78 citations
  2. Candidate Obfuscation via Oblivious LWE SamplingHoeteck Wee, Daniel WichsEUROCRYPT 2021 · 78 citations
  3. The Measure-and-Reprogram Technique 2.0: Multi-round Fiat-Shamir and MoreJelle Don, Serge Fehr, Christian MajenzCRYPTO 2020 · 61 citations
  4. Indistinguishability Obfuscation Without Maps: Attacks and Fixes for Noisy Linear FEShweta Agrawal, Alice Pellet-MaryEUROCRYPT 2020 · 51 citations
  5. One-shot signatures and applications to hybrid quantum/classical authenticationRyan Amos, Marios Georgiou, Aggelos Kiayias, Mark ZhandrySTOC 2020 · 6 citations

Related papers

  1. Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROMJelle Don, Serge Fehr, Christian Majenz, Christian SchaffnerCRYPTO 2022 · 15 citations
  2. Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only IndifferentiabilityMihir Bellare, Hannah Davis, Felix GüntherEUROCRYPT 2020 · 35 citations
  3. The Impossibility of Post-quantum Public Indifferentiability for Merkle-DamgårdAkinori HosoyamadaCRYPTO 2026
  4. Augmented Random OraclesMark ZhandryCRYPTO 2022 · 7 citations
  5. Online-Extractability in the Quantum Random-Oracle ModelJelle Don, Serge Fehr, Christian Majenz, Christian SchaffnerEUROCRYPT 2022 · 57 citations
Dusk over the sea between two cliffs drawn in fine vertical lines