Paper 2025/1889 Original: eprint.iacr.org/2025/1889 ↗
Gluing Random Unitaries with Inverses and Applications to Strong Pseudorandom Unitaries
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.
Metadata
- Available format(s)
PDF- Category
- Foundations
- Publication info
- Preprint.
- History
- 2025-10-09: last updated
- 2025-10-09: published
- Short URL
- https://ia.cr/2025/1889
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2025/1889}
}