[Resource Topic] 2023/543: Pseudorandomness with Proof of Destruction and Applications

Welcome to the resource topic for 2023/543

Pseudorandomness with Proof of Destruction and Applications

Authors: Amit Behera, Zvika Brakerski, Or Sattath, Omri Shmueli


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.

ePrint: https://eprint.iacr.org/2023/543

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .