International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Efficient simulation of random states and random unitaries

Authors:
Gorjan Alagic , QuICS, University of Maryland, and NIST, Gaithersburg, Maryland
Christian Majenz , QuSoft and Centrum Wiskunde & Informatica, Amsterdam, The Netherlands
Alexander Russell , Department of Computer Science and Engineering, University of Connecticut
Download:
DOI: 10.1007/978-3-030-45727-3_26 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2020
Abstract: We consider the problem of efficiently simulating random quantum states and random unitary operators, in a manner which is convincing to unbounded adversaries with black-box oracle access. This problem has previously only been considered for restricted adversaries. Against adversaries with an a priori bound on the number of queries, it is well-known that t-designs suffice. Against polynomial-time adversaries, one can use pseudorandom states (PRS) and pseudorandom unitaries (PRU), as defined in a recent work of Ji, Liu, and Song; unfortunately, no provably secure construction is known for PRUs. In our setting, we are concerned with unbounded adversaries. Nonetheless, we are able to give stateful quantum algorithms which simulate the ideal object in both settings of interest. In the case of Haar-random states, our simulator is polynomial-time, has negligible error, and can also simulate verification and reflection through the simulated state. This yields an immediate application to quantum money: a money scheme which is information-theoretically unforgeable and untraceable. In the case of Haar-random unitaries, our simulator takes polynomial space, but simulates both forward and inverse access with zero error. These results can be seen as the first significant steps in developing a theory of lazy sampling for random quantum objects.
Video from EUROCRYPT 2020
BibTeX
@inproceedings{eurocrypt-2020-30236,
  title={Efficient simulation of random states and random unitaries},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  publisher={Springer},
  keywords={Quantum;lazy sampling;randomness;quantum money},
  volume={12105},
  doi={10.1007/978-3-030-45727-3_26},
  author={Gorjan Alagic and Christian Majenz and Alexander Russell},
  year=2020
}