IACR News item: 23 February 2023
James Bartusek, Sanjam Garg, Vipul Goyal, Dakshita Khurana, Giulio Malavolta, Justin Raizes, Bhaskar Roberts
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.