Paper 2021/433

Formations for the Quantum Random Oracle

Aaram Yun


In the quantum random oracle model, the adversary may make quantum superposition queries to the random oracle. Since even a single query can potentially probe exponentially many points, classical proof techniques are hard to be applied. For example, recording the oracle queries seemed difficult. In 2018, Mark Zhandry showed that, despite the apparent difficulties, it is in fact possible to ‘record’ the quantum queries. He has defined the compressed oracle, which is indistinguishable from the quantum random oracle, and records information the adversary has gained through the oracle queries. It is a technically subtle work, which we believe to be a challenging work to grasp fully. Our aim is to obtain a mathemathically clean, simple reinterpretation of the compressed oracle technique. For each partial function, we define what we call the formation and the completion of that partial function. The completions describe what happens to the real quantum random oracle, and the formations describe what happens to the compressed oracle. We will show that the formations are 'isomorphic' to the completions, giving an alternative proof that the compressed oracle is indistinguishable from the quantum random oracle.

Note: Minor updates on notations

Available format(s)
Publication info
Preprint. Minor revision.
quantum random oraclecompressed oracleoracle recordingquantum superposition queryformationcompletionpartial function
Contact author(s)
aaramyun @ ewha ac kr
2021-06-30: last of 2 revisions
2021-04-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Aaram Yun},
      title = {Formations for the Quantum Random Oracle},
      howpublished = {Cryptology ePrint Archive, Paper 2021/433},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.