Paper 2023/1371 Original: eprint.iacr.org/2023/1371 ↗
Oracle Recording for Non-Uniform Random Oracles, and its Applications
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2023-10-18: last updated
- 2023-09-13: published
- Short URL
- https://ia.cr/2023/1371
- License
- https://creativecommons.org/licenses/by-nc-nd/4.0/
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}
}