Welcome to the resource topic for 2024/1524
Title:
Lower Bounds on the Overhead of Indistinguishability Obfuscation
Authors: Zhenjian Lu, Noam Mazor, Igor C. Oliveira, Rafael Pass
Abstract:We consider indistinguishability obfuscation (iO) for multi-output circuits C:\{0,1\}^n\to\{0,1\}^n of size s, where s is the number of AND/OR/NOT gates in C. Under the worst-case assumption that NP \nsubseteq BPP, we establish that there is no efficient indistinguishability obfuscation scheme that outputs circuits of size s + o(s/ \log s). In other words, to be secure, an efficient iO scheme must incur an \Omega(s/ \log s) additive overhead in the size of the obfuscated circuit. The hardness assumption under which this negative result holds is minimal since an optimal iO scheme with no circuit size overhead exists if NP$\nsubseteq$ BPP.
Expanding on this result, we also rule out iO for single-output database-aided circuits with an arbitrary polynomial overhead in circuit size. This strengthens an impossibility result by Goldwasser and Rothblum [GR07], which considered circuits with access to an exponential-length database that the obfuscator has oracle access to; in contrast, our impossibility result holds even w.r.t. polynomial-size databases and even w.r.t. obfuscators that may run in time polynomial in the size of the database (and thus may read the whole database).
The proof of our main result builds on a connection between obfuscation and meta-complexity put forward by Mazor and Pass [MP24], and on the NP-hardness of circuit minimization for multi-output circuits established by Loff, Ilango, and Oliveira [ILO20], together with other techniques from cryptography and complexity theory.
ePrint: https://eprint.iacr.org/2024/1524
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 .