Obfuscation Overhead for Single-Output Circuits
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
An obfuscator makes a program unintelligible; the question here is what that costs in size. If NP is easy there is no cost at all — an optimal obfuscator with zero overhead exists — so any lower bound needs a hardness assumption, and the weakest sensible one is that NP is hard. Under exactly that, the source shows an obfuscator for circuits with many output bits must add \(\Omega(s/\log s)\) gates. Their argument goes through the hardness of deciding whether a multi-output function has a small circuit. For circuits with a single output bit the corresponding hardness question is one of the famous open problems of complexity theory, and the overhead question is open with it.
View PDF · LaTeX source · Formal statement — not yet formalized
The setting. For a circuit \(C\) of size \(s\) — the number of AND/OR/NOT gates — an indistinguishability obfuscator outputs a circuit of size \(\sigma(\lambda,s)\), and the overhead is how much larger that is than \(s\). The hardness assumption cannot be dropped: “The hardness assumption under which this negative result holds is minimal since an optimal iO scheme with no circuit size overhead exists if \(\mathsf{NP} \subseteq \mathsf{BPP}\).”
What is proved (the source’s Theorem 1). Under \(\mathsf{NP} \not\subseteq \mathsf{BPP}\), there is no efficient indistinguishability obfuscation scheme for multi-output circuits \(C : \{0,1\}^n \to \{0,1\}^n\) of size \(s\) that outputs circuits of size \(s + o(s/\log s)\). Equivalently, a secure efficient iO scheme must incur an \(\Omega(s/\log s)\) additive overhead.
Conjecture. The same holds for single-output Boolean circuits: under \(\mathsf{NP} \not\subseteq \mathsf{BPP}\), there is no efficient iO scheme for single-output circuits \(C : \{0,1\}^n \to \{0,1\}\) of size \(s\) that outputs circuits of size \(s + o(s/\log s)\).
How the source states it. Page 12: “As our main open problems, we leave the extension of our (database-free) impossibility results to the setting of single-output circuits, the investigation of iO for multi-output circuits with output size \((1 + \Omega(1)) \cdot s\), and understanding the limits of our approach.” And page 5: “we currently do not know how to establish them for single-output Boolean circuits nor for multi-output circuits where we allow unbounded fan-in gates when measuring circuit size.”
The source names the direction without restating the bound, so the specific form above — same target, same assumption — is this statement’s choice and the natural reading of “extension of our impossibility results”. A partial result at a weaker overhead is progress and should be reported as such.
The obstruction, which is a named open problem. The route needs NP-hardness of a gap version of Multi-MCSP under randomized Levin reductions. For single-output circuits the corresponding statement is the NP-hardness of \(\mathrm{MCSP}\), open for decades. The source is explicit that even its own intermediate step is hard: “This remains a challenging open problem, and can be seen as an important step towards establishing the NP-hardness of MCSP for single-output Boolean functions.”
It also names the technical difficulty: the Multi-MCSP instances produced by the reduction from Set-Cover have the form \(F : \{0,1\}^\ell \to \{0,1\}^m\) with \(m\) of order roughly \(2^\ell\), and padding the input length to \(m\) would require printing a truth-table of size \(2^m\) per coordinate — prohibitively large.
One padding obstacle that was cleared. Easy to conflate with the above, so worth separating. Going from arbitrary multi-output circuits \(C : \{0,1\}^\ell \to \{0,1\}^m\) to the square case \(C : \{0,1\}^n \to \{0,1\}^n\) is solved: “This allows us to establish thorough a simple padding argument that the hardness of iO for arbitrary multi-output circuits … implies its hardness for circuits of the form \(C : \{0,1\}^n \to \{0,1\}^n\).” What remains open is the drop to one output bit, not the shape of the multi-output case.
What the source does prove for single-output circuits. Not nothing, but in a different model: it rules out iO for single-output database-aided circuits with arbitrary polynomial overhead, strengthening Goldwasser and Rothblum. Where they considered an exponential-length database accessed by oracle, the source’s result holds even for polynomial-size databases and against obfuscators that may read the whole database. This conjecture is the database-free case — hence the source’s phrase “our (database-free) impossibility results”.
Sources
- Lu, Mazor, Oliveira and Pass. Lower Bounds on the Overhead of Indistinguishability Obfuscation. IACR ePrint 2024/1524. The source. The main theorem and database-aided result are in the abstract and Section 1; the single-output remark is on page 5; the MCSP obstruction and padding argument on page 8; the main open problems on page 12; the bottleneck remark on page 33.
- Mazor and Pass. Gap MCSP is not (Levin) NP-complete in Obfustopia. CCC 2024. The obfuscation–meta-complexity connection the source turns on its head to prove impossibility.
- Ilango, Loff and Oliveira. NP-hardness of Circuit Minimization for Multi-Output Functions. CCC 2020. The Multi-MCSP hardness the source extends to a gap version — and whose single-output analogue is the obstruction.
- Goldwasser and Rothblum. On Best-Possible Obfuscation. TCC 2007. The database-aided impossibility the source strengthens.
View PDF — no proof written yet · LaTeX source — no proof written yet · Formal proof — not yet formalized
Open, and blocked on a barrier problem.
Why the route is blocked. The proof reinterprets Mazor and Pass — who showed iO plus sub-exponentially secure one-way functions imply a gap version of \(\mathrm{MCSP}\) is not NP-hard under Levin reductions — as a tool for impossibility. That needs a meta-computational problem whose NP-hardness is known, and Multi-MCSP is the only one available. For single-output circuits there is no such problem: NP-hardness of \(\mathrm{MCSP}\) is precisely what is missing, and by the source’s own assessment its intermediate step would already be “an important step towards” it. So a proof by this route carries a major complexity result with it.
The way out, if there is one. A route to obfuscation overhead lower bounds that does not pass through meta-complexity. None is known, and finding one would be the more interesting outcome than the conjecture itself.
Checked against the literature, 2026-08-28. No single-output overhead lower bound found, and \(\mathrm{MCSP}\) NP-hardness remains open. Targeted check on this line and the meta-complexity results the source builds on, not an exhaustive sweep.
The neighbouring parameter question, with its own named bottleneck. The second of the source’s main open problems is iO for multi-output circuits with output size \((1+\Omega(1))\cdot s\) — a constant multiplicative overhead rather than the additive \(o(s/\log s)\) ruled out. The source locates the bottleneck: “The choice of parameters governing this gap are constrained by the encoding argument presented near the end of the proof, which does not seem to allow an additive gap of the form \(\Omega(s)\).” It also notes the overhead in its Theorems 1 and 2 can be slightly improved, from \(\Omega(s/\log s)\) to \(\Omega(s\log\log s/\log s)\). Different statement, not published here.
Why the assumption is worth noting. \(\mathsf{NP} \not\subseteq \mathsf{BPP}\) is a worst-case assumption, which is unusual for a result about a cryptographic primitive, and it is minimal in the precise sense above. A resolution that needed a stronger assumption would be a materially weaker result.
What a reviewer should be suspicious of, in order. First, whether a claimed result is for single-output or multi-output circuits — the whole content is that distinction. Second, whether it is database-free, since the database-aided single-output case is already settled. Third, whether the size measure is the number of AND/OR/NOT gates, since the source flags that unbounded fan-in is another case it cannot handle.