Paper 2018/544

Pseudorandom Quantum States

Zhengfeng Ji, Yi-Kai Liu, and Fang Song

Abstract

We propose the concept of pseudorandom quantum states, which appear random to any quantum polynomial-time adversary. This offers a computational approximation to perfect randomness on quantum states (analogous to a cryptographic pseudorandom generator), as apposed to some statistical notion of quantum pseudorandomness in the literature, 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 feasibility of our definition. We then prove several basic properties of any pseudorandom states, which further back up our definition. First, we show a cryptographic no-cloning theorem that no efficient quantum algorithm that can create additional copies from any polynomial-many copies of pseudorandom states. 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, thanks to our cryptographic no-cloning theorem.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in CRYPTO 2018
Keywords
pseudorandomnessquantum money
Contact author(s)
Zhengfeng Ji @ uts edu au
yikailiu00 @ gmail com
fsong @ pdx edu
History
2018-06-04: received
Short URL
https://ia.cr/2018/544
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/544,
      author = {Zhengfeng Ji and Yi-Kai Liu and Fang Song},
      title = {Pseudorandom Quantum States},
      howpublished = {Cryptology ePrint Archive, Paper 2018/544},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/544}},
      url = {https://eprint.iacr.org/2018/544}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.