Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries

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

Paper 2025/1889

Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries

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

Gluing theorem for random unitaries [Schuster, Haferkamp, Huang, QIP 2025] have found numerous applications, including designing low depth random unitaries [Schuster, Haferkamp, Huang, QIP 2025], random unitaries in $\mathsf{QAC0}$ [Foxman, Parham, Vasconcelos, Yuen'25] and generically shortening the key length of pseudorandom unitaries [Ananth, Bostanci, Gulati, Lin EUROCRYPT'25]. We present an alternate method of combining 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. As a consequence, we show for the first time that strong pseudorandom 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 any family of strong pseudorandom unitaries exists.

Note: A preliminary version, merging this paper and arXiv:2509.24432, appears in the proceedings of the 45th Annual International Cryptology Conference (CRYPTO 2025) under the title "Pseudorandom Unitaries in the Haar Random Oracle Model". This is Part II of the full version.

Metadata

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

BibTeX

@misc{cryptoeprint:2025/1889,
      author = {Prabhanjan Ananth and John Bostanci and Aditya Gulati and Yao-Ting Lin},
      title = {Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1889},
      year = {2025},
      doi = {10.1007/978-3-032-01878-6_10},
      url = {https://eprint.iacr.org/2025/1889}
}