CryptoDB
Pseudorandom Unitaries in the Haar Random Oracle Model
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | The quantum Haar random oracle model is an idealized model where every party has access to a single Haar random unitary and its inverse. We construct strong pseudorandom unitaries in the quantum Haar random oracle model. This strictly improves upon prior works who either only prove the existence of pseudorandom unitaries in the inverse-less quantum Haar random oracle model [Ananth, Bostanci, Gulati, Lin, EUROCRYPT 2025] or prove the existence of a weaker notion (implied by strong pseudorandom unitaries) in the quantum Haar random oracle model [Hhan, Yamada, 2024]. We also provide an alternate method of joining Haar random unitaries from the gluing lemma from [Schuster, Haferkamp, Huang, QIP 2025] that is secure against adversaries with inverse query access to the joined unitary.Taken together, our results have the following implication for the plain model: strong pseudo-random unitaries can generically have their length extended, and can be constructed using only O(n^(1/c)) bits of randomness, for any constant c, if strong pseudorandom unitaries exists.Our results also present a viable approach for building quantum pseudorandomness from random quantum circuits and analyzing pseudo-random objects in nature. As part of our analysis, we formalize a “strong path-recording framework'', which generalizes the path-recording framework of [Ma, Huang, QIP 2025]. |
BibTeX
@inproceedings{crypto-2025-35724,
title={Pseudorandom Unitaries in the Haar Random Oracle Model},
publisher={Springer-Verlag},
author={Prabhanjan Ananth and John Bostanci and Aditya Gulati and Yao-Ting Lin},
year=2025
}