Publicly-Verifiable Deletion via Target-Collapsing Functions

ePrint Report: Publicly-Verifiable Deletion via Target-Collapsing Functions

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 …

build collision deletion enable eprint report functions hash hashes hash functions james quantum report standard support target