Welcome to the resource topic for 2023/1371
Title:
Oracle Recording for Non-Uniform Random Oracles, and its Applications
Authors: Minki Hhan, Aaram Yun
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 \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.
ePrint: https://eprint.iacr.org/2023/1371
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .