Paper 2023/1371
Oracle Recording for Non-Uniform Random Oracles, and its Applications
, Korea Institute for Advanced Study, Ewha Womans UniversityAbstract
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.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- compressed oraclenonuniform random oracleoracle recordingquantum collsion findingquantum random oracleGrover 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},
note = {\url{https://eprint.iacr.org/2023/1371}},
url = {https://eprint.iacr.org/2023/1371}
}
