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

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)$.

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 .$

Surely $\alpha_{min}$ is asymptotic to 1 as obfuscation is mathematically ill defined. Just how much a circuit can be disguised is pretty indeterminate. Hamming distance, entropy, cycles, etc. That's the main problem facing virus scanners.

Therefore $\frac{L(\mathcal{O}(\mathbf{x},C))}{L(C)}$ can be reduced to virtually 1 if $\mathcal{O}$ tends to a negligible operator leaving $C$ mostly unaffected. Encoding a large program with ROT13 and incorporating a small decoding component would not introduce a large element of complexity. $C$ doesn't have to be made into interpreted metamorphic code inside a custom built virtual machine.

This means that the lowest complexity of the resulting obfuscated circuit can be almost the same as the original. This is the thesis that Garg & Liu prove in Proposition 3 when you equate complexity with entropy. If you also realise that an obfuscated and it's non obfuscated ancestral program cannot possibly be symmetric obfuscations of one another, then it follows that $\alpha \not< 1$.

• This appears to have nothing to do with cryptographic obfuscation. Decoding code at runtime is not an example of indistinguishability obfuscation. Ineffective ad-hoc techniques like that are not what cryptographic obfuscation is concerned with - and this is easy to see when you look at the definition of indistinguishability obfuscation. It doesn't matter whether it's ROT13 or AES with a key embedded in the binary to decrypt at runtime, they don't count and cannot work. – Ella Rose Aug 28 '18 at 0:14
• @EllaRose Perhaps I misread the tag definition in the question. I'll wait for your answer to see how the tag's wrong. – Paul Uszak Aug 28 '18 at 0:22
• @EllaRose From "What is indistinguishability Obfuscation" @ crypto.stackexchange.com/q/44770/23115, it would appear that either the "Software obfuscation" tag is very wrong, or the question is badly phrased mixing up two concepts. – Paul Uszak Aug 28 '18 at 3:26
• There question is not badly phrased or mixing up the two concepts. I can update the tag. – Ella Rose Aug 28 '18 at 3:59
• @EllaRose Sorry, it's the blue link in para.2 of the question. – Paul Uszak Aug 29 '18 at 0:31