International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Pseudorandom Quantum States

Authors:
Zhengfeng Ji
Yi-Kai Liu
Fang Song
Download:
DOI: 10.1007/978-3-319-96878-0_5
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2018
Abstract: We propose the concept of pseudorandom quantum states, which appear random to any quantum polynomial-time adversary. It offers a computational approximation to perfectly random quantum states analogous in spirit to cryptographic pseudorandom generators, as opposed to statistical notions of quantum pseudorandomness that have been studied previously, such as quantum t-designs analogous to t-wise independent distributions.Under the assumption that quantum-secure one-way functions exist, we present efficient constructions of pseudorandom states, showing that our definition is achievable. We then prove several basic properties of pseudorandom states, which show the utility of our definition. First, we show a cryptographic no-cloning theorem: no efficient quantum algorithm can create additional copies of a pseudorandom state, when given polynomially-many copies as input. Second, as expected for random quantum states, we show that pseudorandom quantum states are highly entangled on average. Finally, as a main application, we prove that any family of pseudorandom states naturally gives rise to a private-key quantum money scheme.
Video from CRYPTO 2018
Video provided under Creative Commons / CC BY 3.0
BibTeX
@inproceedings{crypto-2018-28809,
  title={Pseudorandom Quantum States},
  booktitle={Advances in Cryptology – CRYPTO 2018},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  volume={10993},
  pages={126-152},
  doi={10.1007/978-3-319-96878-0_5},
  author={Zhengfeng Ji and Yi-Kai Liu and Fang Song},
  year=2018
}