International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Publicly-Verifiable Deletion via Target-Collapsing Functions

Authors:
James Bartusek , UC Berkeley
Dakshita Khurana , UIUC
Alexander Poremba , Caltech
Download:
DOI: 10.1007/978-3-031-38554-4_4 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: This work re-examines the goal of building cryptosystems with publicly-verifiable deletion. We introduce target-collapsing as a weakening of collapsing, 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, proving conjectures from [Poremba, ITCS'23] and demonstrating that the Dual-Regev encryption (and corresponding FHE) schemes support $\PVD$ under the learning with errors assumption. We build on this framework to obtain a variety of primitives supporting publicly-verifiable deletion ($\PVD$) from weak cryptographic assumptions, including: - Commitments with $\PVD$ assuming the existence of injective one-way functions, or more generally, {\em almost-regular} one-way functions. Along the way, we demonstrate that (partial) 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. - Public-key encryption with $\PVD$ assuming pseudorandom group actions, by demonstrating that the scheme of [Hhan, Morimae, and Yamakawa, Eurocrypt'23] 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.
BibTeX
@inproceedings{crypto-2023-33154,
  title={Publicly-Verifiable Deletion via Target-Collapsing Functions},
  publisher={Springer-Verlag},
  doi={10.1007/978-3-031-38554-4_4},
  author={James Bartusek and Dakshita Khurana and Alexander Poremba},
  year=2023
}