Are there lower bounds to how efficient one can make obfuscated code?

Question

I am wondering if there are any theoretical reasons why obfuscated programs cannot be nearly as efficient as the plaintext programs and whether there is any necessary computational overhead from running obfuscated code instead of plaintext code.

Let $\mathcal{O}$ denote an indistinguishability obfuscator; for each circuit $C$ and random data $\mathbf{x}$, $\mathcal{O}(\mathbf{x},C)$ is an obfuscated circuit that computes the same function as $C$. Is it possible that the obfuscator $\mathcal{O}$ only increases the depth, width or gate count of the circuit $C$ by a linear factor? If not, then what level of complexity overhead is required for the obfuscated circuit $\mathcal{O}(\mathbf{x},C)$? In other words, given a measure $L$ of the complexity of a circuit (for example, $L(C)$ could denote the depth of the circuit $C$), does there exist a constant $\alpha$ and an obfuscator $\mathcal{O}$ where $L(C)\leq\alpha\cdot L(\mathcal{O}(\mathbf{x},C))$ for each circuit $C$ and string $\mathbf{x}$? For which functions $f$ and complexity measures $L$ does there exist a constant $\alpha$ and an obfuscator $\mathcal{O}$ such that $L(C)\leq \alpha\cdot f(\alpha\cdot L(O(\mathbf{x},C)))$ for each circuit $C$ and string $\mathbf{x}$?

I am not very much interested in the computational complexity of the obfuscation operator $\mathcal{O}$ (as long as the obfuscator $\mathcal{O}$ terminates in polynomially many steps), but I am instead interested only in the complexity of the resulting obfuscated circuit $\mathcal{O}(\mathbf{x},C)$.

Answer 1

tl;dr- No, in a general model, there's no lower bound except simply that $\alpha \ge 0.$ The easiest way to see this is to consider the fact that, in the general case, the property of one program being an obfuscation of another implies that the first program is also an obfuscation of the second. Likewise, two differently generated obfuscations of the same programs are also obfuscations of each other.

To get a more practical bound $\alpha$ for use in real-world analysis, a more restrictive model for allowed programs and computers would have to be adopted, as the general case doesn't offer any such bound.

---

Proof that obfuscation doesn't imply a performance hit in the general case

An obfuscated program can be arbitrarily more efficient than a non-obfuscated one, i.e. $\alpha \to 0 .$

The quick proof is to consider the symmetry of obfuscation. For example, consider a family of mutually indistinguishable obfuscations of the same program, e.g.$$ C_{i+1}~=~\mathcal{O}\left(C_i\right) \,. {}^{\phantom{-1}} {\rlap{\qquad \forall i \in \mathbb{N}}} \tag{1} $$Now we've got an infinite set of programs that're mutually indistinguishable; and, assuming that $\mathcal{O}\left(\phantom{C}\right)$ tends to cause a hit in performance, then the performance of an obfuscated program $C_i$ becomes arbitrarily poor as $i \to \infty .$

We can then redescribe this family as$$ C_{i}~=~\mathcal{O}^{-1}\left(C_{i+1}\right) \, , {\rlap{\qquad \forall i \in \mathbb{N}}} \tag{2} $$where we're basically flipping which programs we describe as obfuscations of the others.

While that symmetry argument's probably the easiest, we can also note that obfuscation can include a robust optimization step or something to get $\alpha$ down.

So, in short, no, there's no practical lower bound for $\alpha$ beyond $0$ in the general case. If you're interested in finding practical bounds for $\alpha$ for use in real-world scenarios, then special-case models will need to be assumed rather than the general case.

---

Pedantic: Obfuscation could cause a program to be instant

Consider a program

DoHaltingProblem();
Print("Done!");

If an obfuscator can prove that the halting problem doesn't halt (noting that the issue of halting is incomplete, such that the property of being a halting problem is observer-subjective), then it knows that Print("Done!"); will never execute, allowing it to produce an empty-program

// Literally no instructions to perform

that an observer that perceives the program as containing a halting problem can't knowingly determine to be equivalent. Then, technically, $\alpha = 0 .$

Kinda pedantic, but I guess that I just felt weird writing $\alpha > 0 .$