Paper 2024/1848
Non-Interactive Zero-Knowledge Proofs with Certified Deletion
Abstract
We introduce the notion of non-interactive zero-knowledge (NIZK) proofs with certified deletion. Our notion enables the recipient of a quantum NIZK proof for a (quantumly hard) NP statement to delete the proof and collapse it into a classical deletion certificate. Once this certificate is successfully validated, we require the recipient of the proof to lose their ability to find accepting inputs to NIZK verification. We formally define this notion and build several candidate constructions from standard cryptographic assumptions. In particular, we propose a primary construction from classical NIZK for NP and one-way functions, albeit with two limitations: (i) deletion certificates are only privately verifiable, and (ii) both prover and verifier are required to be quantum algorithms. We resolve these hurdles in two extensions that assume the quantum hardness of the learning with errors problem. The first one achieves publicly verifiable certificates, and the second one requires merely classical communication between classical provers and quantum verifiers.
Metadata
- Available format(s)
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- quantum cryptographycertified deletionrevocable cryptographyzero-knowledge proofsanonymous credentials
- Contact author(s)
-
kasraz @ umd edu
jkatz2 @ gmail com - History
- 2024-11-11: approved
- 2024-11-11: received
- See all versions
- Short URL
- https://ia.cr/2024/1848
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/1848, author = {Kasra Abbaszadeh and Jonathan Katz}, title = {Non-Interactive Zero-Knowledge Proofs with Certified Deletion}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/1848}, year = {2024}, url = {https://eprint.iacr.org/2024/1848} }