International Association for Cryptologic Research

International Association
for Cryptologic Research


Cryptography with Certified Deletion

James Bartusek , UC Berkeley
Dakshita Khurana , University of Illinois Urbana-Champaign
DOI: 10.1007/978-3-031-38554-4_7 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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 \emph{all} parties in this setting is known to be impossible, we introduce {\em everlasting security transfer (EST)}. This enables \emph{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 {\em information-theoretically deleted} from an adversary's view once they output a valid deletion certificate, despite having been previously {\em information-theoretically determined} by the ciphertext they held in their view. This technique may be of independent interest.
  title={Cryptography with Certified Deletion},
  author={James Bartusek and Dakshita Khurana},