Paper 2024/1848

Non-Interactive Zero-Knowledge Proofs with Certified Deletion

Kasra Abbaszadeh, University of Maryland, College Park
Jonathan Katz, Google (United States), University of Maryland, College Park
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)
PDF
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
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.