International Association for Cryptologic Research

International Association
for Cryptologic Research


Software with Certified Deletion

James Bartusek , UC Berkeley
Vipul Goyal , CMU and NTT Research
Dakshita Khurana , UIUC
Giulio Malavolta , Bocconi University and Max Planck Institute for Security and Privacy
Justin Raizes , CMU
Bhaskar Roberts , UC Berkeley
Search ePrint
Search Google
Presentation: Slides
Conference: EUROCRYPT 2024
Abstract: Is it possible to prove the deletion of a computer program after having executed it? While this task is clearly impossible using classical information alone, the laws of quantum mechanics may admit a solution to this problem. In this work, we propose a new approach to answer this question, using quantum information. In the interactive settings, we present the first fully-secure solution for blind delegation with certified deletion, assuming post-quantum hardness of the learning with errors (LWE) problem. In the non-interactive settings, we propose a construction of obfuscation with certified deletion, assuming post-quantum iO and one-way functions. Our main technical contribution is a new deletion theorem for subspace coset states [Vidick and Zhang, EUROCRYPT'21, Coladangelo et al., CRYPTO'21], which enables a generic compiler that adds the certified deletion guarantee to a variety of cryptographic primitives. In addition to our main result, this allows us to obtain a host of new primitives, such as functional encryption with certified deletion and secure software leasing for an interesting class of programs. In fact, we are able for the first time to achieve a stronger notion of secure software leasing, where even a dishonest evaluator cannot evaluate the program after returning it.
  title={Software with Certified Deletion},
  author={James Bartusek and Vipul Goyal and Dakshita Khurana and Giulio Malavolta and Justin Raizes and Bhaskar Roberts},