Indistinguishability Obfuscation — wait, what?
I’ve been writing about Zero Knowledge technology and its usages for quite some time. It’s super interesting technology, but there’s a new, bolder kid on the block: Indistinguishability Obfuscation (iO).
Let me give you a brief intro to what it is and how it can be used — without going into the heavy research behind it.
What is obfuscation
Imagine you have a program. For privacy reasons you don’t want anyone to be able to read or analyze the program’s logic, but they should still be able to use it. The program should remain truly as a black box for its users.
One way to make analysis harder is to obfuscate the program code. Obfuscation keeps the functionality the same but makes the code harder to understand for humans.
How can we obfuscate
There exist various ways to (naively) obfuscate program code.
For languages that are not compiled (like JavaScript), the code can be obfuscated to look like garbage. It looks like garbage but functions the same way as earlier.
For languages that are compiled to another format before execution (typically a binary format), obfuscation happens rather automatically: it’s a lot harder to analyze the compiled version than its source code. But this is just a by-product and not done for privacy reasons.
One can, however, add another layer of explicit obfuscation for compiled languages. The obfuscation can be added either before compilation or after it. Or even both.
Usually it’s not worth it
Obfuscation helps keep your business logic private. This makes sense when the logic is what keeps your company alive, but usually it’s just not worth it.
Any meaningful amount of code obfuscation affects the performance: every layer of extra scrambling makes the code slower to run. Furthermore, it makes the program a lot bigger and harder to distribute.
It usually makes sense to just keep your code as it is, unless you have a real business need for secrecy.
Is obfuscation secure?
So you have important business logic in your code and decided to obfuscate it. Is it now safe?
No.
You can obfuscate in many different ways, but in the end it’s just obfuscation — it’s not cryptographically secure. If there is an adversary with enough time and resources, they can dig out your super secret logic.
But can we make it secure?
Indistinguishability Obfuscation
Say you have two programs A
and B
that always give the same output for the same input. Their internal logic may differ. An example could be sorting an array of elements: there are many ways to perform this operation.
If we apply obfuscation logic O
to both, they become O(A)
and O(B)
. The obfuscation is said to be indistinguishable if one cannot tell which one is which: whether O(A)
utilizes logic A
or B
.
This property also implies that the obfuscation can’t be reversed: all of the secrets remain secrets.
However, there’s a minor glitch: this kind of obfuscation hasn’t been possible. It can be done in theory, but practicality is trickier.
So the current academic challenge is to figure out a realistic implementation for Indistinguishability Obfuscation (iO). Work is ongoing on this front.
Doesn’t sound very exciting
Even if iO becomes reality, it sounds boring. Someone can hide their business logic and that’s it, right?
What if I told you that iO can be used for a lot of modern cryptography? And it can even be used to replace many existing protocols?
Can iO replace Zero Knowledge technology?
Zero Knowledge technology (ZK) allows one to prove the existence of certain data, without revealing the data itself. A proof is generated for the data, and this proof can be verified by anyone with a special verifier program.
A similar result can be obtained with iO: the data to be proven (for example, a password) can be placed inside the program. A verifier inputs the same data and the program outputs true or false, depending on whether the input matched the stored data. But the hardcoded data remains obfuscated inside the program.
If you want to verify something without knowing the actual data (for example, factorization of a large integer), the iO program can provide a commitment to the data and responses to challenges — just like a ZK prover in an interactive protocol.
Can iO replace Fully Homomorphic Encryption?
Fully Homomorphic Encryption (FHE) allows performing calculations on encrypted data.
With FHE, someone with private data can encrypt it, send the encrypted version for others to do computations on and return a new (still encrypted) value. The original party can then decrypt the received data and see the results of the computations.
As expected, this can be accomplished with iO. The program should include both the encryption key and the decryption key. The program does the following:
- Takes encrypted data as input
- Decrypts the data
- Performs calculations on it
- Encrypts the result
- Outputs the re-encrypted data
Since the obfuscation can’t be reversed, the keys remain private inside the program and the program can perform similar operations to FHE.
However, real FHE is much more versatile: it doesn’t need a special program for each different calculation. Much easier to use.
It’s more like a Swiss army knife
Unsurprisingly, iO is not a silver bullet.
Many of the operations performed with iO are very cost-inefficient and cumbersome. Special programs are typically needed for each use case, with very little genericity.
But the main point is that iO can be used instead of many other cryptographic means. Once practical iO becomes a reality, it may make sense to replicate some of the existing cryptography with iO — simply because it’s so versatile.
Using iO is like using a Swiss army knife for all of your kitchen needs. It can be used even if it’s not really efficient for any of that. But it may still make sense before more effective tools are acquired.
What’s next
As mentioned already, there is no practical iO. Yet.
It’s probably just a matter of time. The first implementations will be horribly inefficient. They’ll get better.
This is again one more rabbit hole where you can get lost. If you’re interested, we started a Telegram group for people interested in iO. Its not-so-iO-obfuscated link is 0ADMzMk1lkmZMIyY+/em.t//:sptth.
Thanks
Thanks to Killari and Filip Laurentiu for reviewing this article and discussing the possibilities of iO.
About the author
I’m a ZK & EVM freelancer. I do development and write mostly about Zero Knowledge topics and ecosystems. Wanna have a chat? Get in touch!