Paper 2024/1848

Non-Interactive Zero-Knowledge Proofs with Certified Deletion

Kasra Abbaszadeh, University of Maryland, College Park
Jonathan Katz, Google (United States)
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 to delete the proof and obtain a (classical) certificate proving such deletion. We define this notion and propose two candidate constructions from standard cryptographic assumptions. Our first construction is based on classical NIZK proofs and quantum-hard one-way functions but needs both the prover and verifier to run quantum algorithms. We then present an extension that allows the prover to be classical; this is based on the learning with errors problem and requires an instance-independent interactive setup between the prover and verifier. Our results have applications to revocable signatures of knowledge and revocable anonymous credentials, which we also define and construct.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
quantum cryptographycertified deletionrevocable cryptographyzero-knowledge proofsanonymous credentials
Contact author(s)
kasraz @ umd edu
jkatz2 @ gmail com
History
2025-03-16: last of 3 revisions
2024-11-11: received
See all versions
Short URL
https://ia.cr/2024/1848
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.