International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Quantum Pseudorandom Scramblers

Authors:
Chuhan Lu , Portland State University
Minglong Qin , Nanjing University
Fang Song , Portland State University
Penghui Yao , Nanjing University
Mingnan Zhao , Nanjing University
Download:
Search ePrint
Search Google
Conference: TCC 2024
Abstract: Quantum pseudorandom state generators (PRSGs) have stimulated exciting developments in recent years. A PRSG, on a fixed initial (e.g., all-zero) state, produces an output state that is computationally indistinguishable from a Haar random state. However, pseudorandomness of the output state is not guaranteed on other initial states. In fact, known PRSG constructions provably fail on some initial states. In this work, we propose and construct quantum Pseudorandom State Scramblers (PRSSs), which can produce a pseudorandom state on an arbitrary initial state. In the information-theoretical setting, we obtain a scrambler which maps an arbitrary initial state to a distribution of quantum states that is close to Haar random in total variation distance. As a result, our scrambler exhibits a dispersing property. Loosely, it can span an ɛ-net of the state space. This significantly strengthens what standard PRSGs can induce, as they may only concentrate on a small region of the state space provided that average output state approximates a Haar random state. Our PRSS construction develops a parallel extension of the famous Kac's walk, and we show that it mixes exponentially faster than the standard Kac's walk. This constitutes the core of our proof. We also describe a few applications of PRSSs. While our PRSS construction assumes a post-quantum one-way function, PRSSs are potentially a weaker primitive and can be separated from one-way functions in a relativized world similar to standard PRSGs.
BibTeX
@inproceedings{tcc-2024-34723,
  title={Quantum Pseudorandom Scramblers},
  publisher={Springer-Verlag},
  author={Chuhan Lu and Minglong Qin and Fang Song and Penghui Yao and Mingnan Zhao},
  year=2024
}