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

Minki Hhan; Aaram Yun

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

Abstract

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 ${CStO}_{D}$ and ${CPhsO}_{D}$ , which are indistinguishable to the non-uniform quantum random oracle where quantum access is given to a random function $H$ whose images are sampled from a probability distribution independently for each . 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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: compressed oracle nonuniform random oracle oracle recording quantum collsion finding quantum random oracle Grover search
Contact author(s): minkihhan @ kias re kr
aaramyun @ ewha ac kr
History: 2023-10-18: last of 2 revisions; 2023-09-13: received; See all versions
Short URL: https://ia.cr/2023/1371
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2023/1371,
      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},
      url = {https://eprint.iacr.org/2023/1371}
}