Paper 2023/543

Pseudorandomness with Proof of Destruction and Applications

Amit Behera, Ben-Gurion University of the Negev
Zvika Brakerski, Weizmann Institute of Science
Or Sattath, Ben-Gurion University of the Negev
Omri Shmueli, Tel Aviv University

Two fundamental properties of quantum states that quantum information theory explores are pseudorandomness and provability of destruction. We introduce the notion of quantum pseudorandom states with proofs of destruction (PRSPD) that combines both these properties. Like standard pseudorandom states (PRS), these are efficiently generated quantum states that are indistinguishable from random, but they can also be measured to create a classical string. This string is verifiable (given the secret key) and certifies that the state has been destructed. We show that, similarly to PRS, PRSPD can be constructed from any post-quantum one-way function. As far as the authors are aware, this is the first construction of a family of states that satisfies both pseudorandomness and provability of destruction. We show that many cryptographic applications that were shown based on PRS variants using quantum communication can be based on (variants of) PRSPD using only classical communication. This includes symmetric encryption, message authentication, one-time signatures, commitments, and classically verifiable private quantum coins.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2023
Quantum CryptographyPseudorandom Quantum States
Contact author(s)
behera @ post bgu ac il
zvika brakerski @ weizmann ac il
sattath @ bgu ac il
omrishmueli @ mail tau ac il
2023-09-20: last of 2 revisions
2023-04-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Amit Behera and Zvika Brakerski and Or Sattath and Omri Shmueli},
      title = {Pseudorandomness with Proof of Destruction and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2023/543},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.