Paper 2023/265

Obfuscation and Outsourced Computation with Certified Deletion

James Bartusek, UC Berkeley
Sanjam Garg, UC Berkeley, NTT Research
Vipul Goyal, CMU, NTT Research
Dakshita Khurana, UIUC
Giulio Malavolta, Max Planck Institute for Security and Privacy
Justin Raizes, CMU
Bhaskar Roberts, UC Berkeley

Can we outsource computation on encrypted data, while ensuring that the data is certifiably, information-theoretically deleted by the server after computation? Can we encode a computer program in a manner that preserves its functionality, while allowing an evaluator to {\em prove that they deleted the program}? This work answers the above questions, providing the first fully (maliciously) secure solution to the question of blind delegation with certified deletion, and the first solution to the question of obfuscation with certified deletion. Unlike prior work on deletion, these settings require security in the presence of repeated access to partial decryptions of encoded data, followed by certified deletion of the (rest of the) encoded data. To enable security, we introduce a powerful new paradigm for secure information-theoretic deletion of data based on quantum \emph{subspace coset states}. We obtain the following results. Blind Delegation with Certified Deletion - Assuming the quantum hardness of learning with errors, we obtain maliciously-secure blind delegation with certified deletion. This improves upon prior protocols by Poremba (ITCS 2023) and Bartusek and Khurana (arXiv 2022) that we show are insecure against a malicious server. - Assuming sub-exponentially quantum-secure indistinguishability obfuscation, we obtain a \emph{two-message} protocol for blind delegation with certified deletion. All previous protocols required multiple rounds of interaction between the client and server. Obfuscation with Certified Deletion - Assuming post-quantum indistinguishability obfuscation, we obtain a construction of differing-inputs obfuscation with certified deletion, for a polynomial number of differing inputs. As an immediate corollary, we obtain a strong variant of secure software leasing for every differing-inputs circuit family. - We obtain two flavors of functional encryption with certified deletion, one where ciphertexts can be certifiably deleted, and the other where secret keys can be certifiably deleted, assuming appropriate variants of indistinguishability obfuscation and other standard assumptions. - We show how to prepare an ``oracle with certified deletion'' implementing any efficient classical functionality. Additional Results - Assuming post-quantum CCA-secure public-key encryption, we obtain a notion of CCA-secure public-key encryption with certified deletion. We view this primarily as a pedagogical tool towards understanding our technique. - Assuming post-quantum indistinguishability obfuscation, we show how to generically add a \emph{publicly-verifiable} certified deletion property to a variety of cryptosystems. Publicly-verifiable deletion schemes prior to our work either relied on unproven conjectures (Poremba, ITCS 2023) or structured oracles (Hiroka et al., Asiacrypt 2021). All our primitives satisfy {\em everlasting security after deletion}, except for functional encryption with deletion for secret keys, where a computational certified deletion guarantee is inherent.

Note: Comparisons to concurrent work and clarifications.

Available format(s)
Publication info
ObfuscationDelegationCertified deletion
Contact author(s)
bartusek james @ gmail com
sanjamg @ berkeley edu
vipul @ cmu edu
dakshita @ illinois edu
giulio malavolta @ hotmail it
jraizes @ andrew cmu edu
bhaskarr @ eecs berkeley edu
2023-04-11: revised
2023-02-22: received
See all versions
Short URL
No rights reserved


      author = {James Bartusek and Sanjam Garg and Vipul Goyal and Dakshita Khurana and Giulio Malavolta and Justin Raizes and Bhaskar Roberts},
      title = {Obfuscation and Outsourced Computation with Certified Deletion},
      howpublished = {Cryptology ePrint Archive, Paper 2023/265},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.