[Resource Topic] 2023/370: Publicly-Verifiable Deletion via Target-Collapsing Functions

Welcome to the resource topic for 2023/370

Publicly-Verifiable Deletion via Target-Collapsing Functions

Authors: James Bartusek, Dakshita Khurana, Alexander Poremba


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.

ePrint: https://eprint.iacr.org/2023/370

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .