Paper 2022/1178

Cryptography with Certified Deletion

James Bartusek, University of California, Berkeley
Dakshita Khurana, University of Illinois Urbana-Champaign

We propose a new, unifying framework that yields an array of cryptographic primitives with certified deletion. These primitives enable a party in possession of a quantum ciphertext to generate a classical certificate that the encrypted plaintext has been information-theoretically deleted, and cannot be recovered even given unbounded computational resources. - For $X \in \{\mathsf{public}\text{-}\mathsf{key},\mathsf{attribute\text{-}based},\mathsf{fully\text{-}homomorphic},\mathsf{witness},\mathsf{timed}\text{-}\mathsf{release}\}$, our compiler converts any (post-quantum) $X$ encryption to $X$ encryption with certified deletion. In addition, we compile statistically-binding commitments to statistically-binding commitments with certified everlasting hiding. As a corollary, we also obtain statistically-sound zero-knowledge proofs for QMA with certified everlasting zero-knowledge assuming statistically-binding commitments. - We also obtain a strong form of everlasting security for two-party and multi-party computation in the dishonest majority setting. While simultaneously achieving everlasting security against all parties in this setting is known to be impossible, we introduce everlasting security transfer (EST). This enables any one party (or a subset of parties) to dynamically and certifiably information-theoretically delete other participants' data after protocol execution. We construct general-purpose secure computation with EST assuming statistically-binding commitments, which can be based on one-way functions or pseudorandom quantum states. We obtain our results by developing a novel proof technique to argue that a bit $b$ has been information-theoretically deleted from an adversary's view once they output a valid deletion certificate, despite having been previously information-theoretically determined by the ciphertext they held in their view. This technique may be of independent interest.

Available format(s)
Publication info
Quantum cryptographycertified deletioneverlasting security
Contact author(s)
bartusek james @ gmail com
dakshita @ illinois edu
2023-02-15: last of 2 revisions
2022-09-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {James Bartusek and Dakshita Khurana},
      title = {Cryptography with Certified Deletion},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1178},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.