CryptoDB
The power of a single Haar random state: constructing and separating quantum pseudorandomness
| Authors: |
|
|---|---|
| Download: | |
| Conference: | EUROCRYPT 2025 |
| 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 find that the study of such a model sheds light on several aspects of the notion of quantum pseudorandomness. Pseudorandom states 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. We obtain the following results: 1. First, we show, perhaps surprisingly, that 1PRS (as well as bit-commitments) exist relative to an oracle that provides a single Haar random state. 2. Second, we build on this result to show the existence of a unitary oracle relative to which 1PRS exist, but PRS do not. Taken together, our contributions yield one of the first black-box separations between central notions of quantum pseudorandomness, and introduce a new framework to study black-box separations between various inherently quantum primitives. |
BibTeX
@inproceedings{eurocrypt-2025-35059,
title={The power of a single Haar random state: constructing and separating quantum pseudorandomness},
publisher={Springer-Verlag},
author={Boyang Chen and Andrea Coladangelo and Or Sattath},
year=2025
}