Yao-Ting Lin

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 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 strong pseudorandom unitaries exists.

Common random string model is a popular model in classical cryptography with many constructions proposed in this model. We study a quantum analogue of this model called the common Haar state model, which was also studied in an independent work by Chen, Coladangelo and Sattath (arXiv 2024). In this model, every party in the cryptographic system receives many copies of one or more i.i.d Haar states. Our main result is the construction of a statistically secure pseudorandom function-like state generator (PRFSG) in the common Haar state model. Our construction satisfies stretch property (output length > $\lambda$), can handle inputs of length $\lambda^{c}$ and is secure as long as the adversary gets $O\left(\frac{\lambda^{1-c}}{(\log(\lambda))^{1.01}} \right)$ number of queries, where $\lambda$ is the length of the PRFSG key and $c \in [0,1)$. We show the optimality of our construction by proving a matching lower bound. As a consequence, for the first time, we show that (computationally secure) PRFSGs for super-logarithmic input length can be constructed from (computationally secure) pseudorandom state generators in some parameter regimes.