Paper 2023/1371

Oracle Recording for Non-Uniform Random Oracles, and its Applications

Minki Hhan, Korea Institute for Advanced Study
Aaram Yun, Ewha Womans University

In Crypto 2019, Zhandry showed how to define compressed oracles, which record quantum superposition queries to the quantum random oracle. In this paper, we extend Zhandry's compressed oracle technique to non-uniformly distributed functions with independently sampled outputs. We define two quantum oracles $\mathsf{CStO}_D$ and $\mathsf{CPhsO}_D$, which are indistinguishable to the non-uniform quantum random oracle where quantum access is given to a random function $H$ whose images $H(x)$ are sampled from a probability distribution $D$ independently for each $x$. We show that these compressed oracles record the adversarial quantum superposition queries. Also, we re-prove the optimality of Grover search and the collision resistance of non-uniform random functions, using our extended compressed oracle technique.

Note: In this version, the definition of a morphism is slightly modified, and also we have extended the definition of a quantum oracle to allow the internal oracle state to be mixed. Also there are some minor edits as well.

Available format(s)
Publication info
compressed oraclenonuniform random oracleoracle recordingquantum collsion findingquantum random oracleGrover search
Contact author(s)
minkihhan @ kias re kr
aaramyun @ ewha ac kr
2023-10-18: last of 2 revisions
2023-09-13: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-NoDerivs


      author = {Minki Hhan and Aaram Yun},
      title = {Oracle Recording for Non-Uniform Random Oracles, and its Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1371},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.