Obfuscation and Outsourced Computation with Certified Deletion

Abstract

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.

Available format(s)
Category
Foundations
Publication info
Preprint.
Keywords
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
History
2023-02-23: approved
See all versions
Short URL
https://ia.cr/2023/265

CC0

BibTeX

@misc{cryptoeprint:2023/265,
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{https://eprint.iacr.org/2023/265}},
url = {https://eprint.iacr.org/2023/265}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.