International Association
for Cryptologic Research

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.

We develop a simple compiler that generically adds publicly-verifiable deletion to a variety of cryptosystems. Our compiler only makes use of one-way functions (or one-way state generators, if we allow the public verification key to be quantum). Previously, similar compilers either relied on indistinguishability obfuscation along with any one-way function (Bartusek et. al., ePrint:2023/265), or on almost-regular one-way functions (Bartusek, Khurana and Poremba, CRYPTO 2023).

Quantum cryptography leverages many unique features of quantum information in order to construct cryptographic primitives that are oftentimes impossible classically. In this work, we build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities. We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before. We define and construct several fundamental cryptographic primitives with key-revocation capabilities, namely pseudorandom functions, secret-key and public-key encryption, and even fully homomorphic encryption. Our constructions either assume the quantum subexponential hardness of the learning with errors problem or are based on new conjectures. Central to all our constructions is our approach for making the Dual-Regev encryption scheme (Gentry, Peikert and Vaikuntanathan, STOC 2008) revocable.