Pseudorandom Unitaries in the Haar Random Oracle Model

Prabhanjan Ananth; John Bostanci; Aditya Gulati; Yao-Ting Lin

Paper 2025/1784

Pseudorandom Unitaries in the Haar Random Oracle Model

Prabhanjan Ananth, University of California, Santa Barbara

John Bostanci, Columbia University

Aditya Gulati, University of California, Santa Barbara

Yao-Ting Lin, University of California, Santa Barbara

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 inverseless 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]. Our results also present a viable approach for building quantum pseudorandomness from random quantum circuits and analyzing pseudorandom objects in nature.

Note: A preliminary version of this paper appears in the proceedings of the 45th Annual International Cryptology Conference (CRYPTO 2025). This is Part I of the full version.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in CRYPTO 2025
Contact author(s): prabhanjan @ cs ucsb edu
johnb @ cs columbia edu
adityagulati @ ucsb edu
yao-ting_lin @ ucsb edu
History: 2025-10-03: approved; 2025-09-29: received; See all versions
Short URL: https://ia.cr/2025/1784
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1784,
      author = {Prabhanjan Ananth and John Bostanci and Aditya Gulati and Yao-Ting Lin},
      title = {Pseudorandom Unitaries in the Haar Random Oracle Model},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1784},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1784}
}