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.