International Association
for Cryptologic Research

We introduce the notion of non-interactive zero-knowledge (NIZK) arguments with certified deletion, a new primitive that enables the recipient of a (quantum) NIZK argument to delete it and obtain a (classical) certificate proving such deletion. We formalize this notion and propose two candidate constructions from standard cryptographic assumptions. Our first construction is based on classical NIZK arguments and quantum-hard one-way functions, but requires both the prover and verifier to run quantum algorithms. We then present an extension based on the learning with errors problem that allows the prover to be classical. Our results have applications to signatures of knowledge and anonymous credentials with certified deletion, which we also define and construct.