Welcome to the resource topic for 2022/1178
Title:
Cryptography with Certified Deletion
Authors: James Bartusek, Dakshita Khurana
Abstract:We propose a new, unifying framework that yields an array of cryptographic primitives with {\em 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 yields post-quantum X encryption with certified deletion, assuming post-quantum X encryption. Assuming the existence of statistically-binding commitments, our compiler yields statistically-binding commitments with certified everlasting hiding as well as statistically-sound zero-knowledge proofs for QMA with certified everlasting zero-knowledge. We also introduce and construct information-theoretic secret sharing with certified deletion.
While encryption with certified deletion was first introduced by Broadbent and Islam (TCC 2020) in the context of an information-theoretic one-time pad, existing proposals by Unruh (Eurocrypt 2014), Hiroka et al. (Asiacrypt 2021), Hiroka et al. (Crypto 2021), and Poremba (QIP 2022) for {\em public-key} primitives with certified deletion (1) have complex tailored constructions and non-generic proofs, (2) are not known to satisfy everlasting security after deletion in the plain model, and in many cases (3) resort to idealized models or stronger cryptographic assumptions like obfuscation. We remedy this situation 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 produce a valid deletion certificate, despite having been previously {\em information-theoretically determined} by the ciphertext they held in their view. This may be of independent interest.
Finally, we take the notion of certified deletion a step further, and explore its implications in the context of mistrustful two-(and multi-)party cryptography. Here, there is a strong impossibility result by Unruh (Crypto 2013) building on Lo, Chau, and Mayers (Physical Review Letters) showing that everlasting security against \emph{every} party is impossible to achieve, even with quantum communication, and even if parties are computationally bounded during the protocol. Nevertheless, we introduce the notion of \emph{Everlasting Security Transfer}, enabling participants to dynamically request that \emph{any} party (or parties) information-theoretically delete their data, even \emph{after} the protocol execution completes. We show how to construct secure two-party and multi-party computation satisfying this notion of security, which is impossible to achieve in a classical world. Our constructions all assume only statistically-binding commitments, which can be built from one-way functions or pseudo-random quantum states.
ePrint: https://eprint.iacr.org/2022/1178
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .