Contributed Talks 2c

Abstract: Uniformly random unitaries, i.e. unitaries drawn from the Haar measure, have many useful properties but cannot be implemented efficiently. This has motivated a long line of research into random unitaries that ``look'' sufficiently Haar random while also being efficient to implement. Two different notions of derandomisation have emerged: t-designs are random unitaries that information-theoretically reproduce the first t moments of the Haar measure, and pseudorandom unitaries (PRUs) are random unitaries that are computationally indistinguishable from Haar random.In this work, we take a unified approach to constructing t-designs and PRUs. For this, we introduce and analyse the ``PFC ensemble'', the product of a computational basis permutation P, a random binary phase operator F, and a random Clifford unitary C. We show that this ensemble reproduces exponentially high moments of the Haar measure. We can then derandomise the PFC ensemble to show the following:-Linear-depth t-designs. We give the first construction of a (diamond-error) approximate t-design with circuit depth linear in t. This follows from the PFC ensemble by replacing the random phase and permutation operators with their 2t-wise independent counterparts. - Non-adaptive PRUs. We give the first construction of PRUs with non-adaptive security, i.e. we construct unitaries that are indistinguishable from Haar random to polynomial-time distinguishers that query the unitary in parallel on an arbitary state. This follows from the PFC ensemble by replacing the random phase and permutation operators with their pseudorandom counterparts. - Adaptive pseudorandom isometries. We show that if one considers isometries (rather than unitaries) from n to n + \omega(log n) qubits, a small modification of our PRU construction achieves adaptive security, i.e.~even a distinguisher that can query the isometry adaptively in sequence cannot distinguish it from Haar random isometries. This gives the first construction of adaptive pseudorandom isometries. Under an additional conjecture, this proof also extends to adaptive PRUs.

Abstract: In this work, we focus on the following question: what are the cryptographic implications of having access to an oracle that provides a single Haar random quantum state? We show, perhaps surprisingly, that such an oracle is sufficient to construct quantum pseudorandomness. Pseudorandom states (PRS) are a family of states for which it is hard to distinguish between polynomially many copies of either a state sampled uniformly from the family or a Haar random state. A weaker notion, called single-copy pseudorandom states (1PRS), satisfies this property with respect to a single copy. Our main result is that 1PRS (as well as bit-commitments) exist relative to an oracle that provides a single Haar random state. We build on this result to show the existence of an oracle relative to which 1PRS exist, but PRS do not. This provides one of the first black-box separations between different forms of quantum pseudorandomness.

Abstract: 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.