Paper 2023/370

Publicly-Verifiable Deletion via Target-Collapsing Functions

James Bartusek, University of California, Berkeley
Dakshita Khurana, University of Illinois Urbana-Champaign
Alexander Poremba, California Institute of Technology

We build quantum cryptosystems that support publicly-verifiable deletion from standard cryptographic assumptions. We introduce target-collapsing as a weakening of collapsing for hash functions, analogous to how second preimage resistance weakens collision resistance; that is, target-collapsing requires indistinguishability between superpositions and mixtures of preimages of an honestly sampled image. We show that target-collapsing hashes enable publicly-verifiable deletion (PVD), proving conjectures from [Poremba, ITCS'23] and demonstrating that the Dual-Regev encryption (and corresponding fully homomorphic encryption) schemes support PVD under the LWE assumption. We further build on this framework to obtain a variety of primitives supporting publicly-verifiable deletion from weak cryptographic assumptions, including: - Commitments with PVD assuming the existence of injective one-way functions, or more generally, almost-regular one-way functions. Along the way, we demonstrate that (variants of) target-collapsing hashes can be built from almost-regular one-way functions. - Public-key encryption with PVD assuming trapdoored variants of injective (or almost-regular) one-way functions. We also demonstrate that the encryption scheme of [Hhan, Morimae, and Yamakawa, Eurocrypt'23] based on pseudorandom group actions has PVD. - $X$ with PVD for $X \in \{$attribute-based encryption, quantum fully-homomorphic encryption, witness encryption, time-revocable encryption$\}$, assuming $X$ and trapdoored variants of injective (or almost-regular) one-way functions.

Available format(s)
Public-key cryptography
Publication info
quantum encryptioncertified deletionpublic verification
Contact author(s)
bartusek james @ gmail com
dakshita @ illinois edu
aporemba @ caltech edu
2023-03-16: approved
2023-03-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {James Bartusek and Dakshita Khurana and Alexander Poremba},
      title = {Publicly-Verifiable Deletion via Target-Collapsing Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/370},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.