Indistinguishability Obfuscation
In: Mathematics
Obfuscation in general is the process of making a program less readable. Often this is done by muddling either the logical structure or the names, such that a human reader will have a harder time understanding what the program is doing.
The optimal obfuscation would be black-box obfuscation – transforming the program in such a way that you cannot get *any* information about what it’s doing other than what you can observe by interacting with it (giving it inputs and seeing what it outputs). This would be the equivalent of putting the program on a remote server, and allowing you to interact with it but never read the source code. A while back, it was proved that this is impossible – if someone has access to the source code, they will always be able to discover at least some information about the program beyond what can be observed by simply interacting with it.
The next best step was indistinguishability obfuscation (which I’ll be calling IND obfuscation for ease of typing). This is a process of transforming a program such that it cannot be differentiated from programs that do the same thing.
Why is this useful? Well, consider two programs that check your password.
def check_password(password):
if password == “my secret key”:
return ALLOW
else:
return DENY
If you have access to this program, you can easily discover the password. However, there is an alternative using [cryptographic hash functions](https://en.wikipedia.org/wiki/Cryptographic_hash_function) – a function that will give the same output for every input, but makes it extremely difficult to discover what that input was if you just get the output. I can create the program:
def check_password_secure(password):
if hash(password) == “b06c1190acfd0eb89e4bb9bb39e0f937536e11e9”:
return ALLOW
else:
return DENY
Now, somebody reading this program *cannot* discover what the correct password is. We’ve hidden some information that could have been obtainable by a person or algorithm analyzing our password checker.
IND obfuscation takes an analogous process and takes it to the logical extreme – it takes a program (technically a circuit, but they are equivalent in many applications) and creates the most obfuscated version of it – any operation that could in principle be replaced with a hidden version is replaced.
At the moment, this is not something that’s practical for everyday programs. The recent construction by Jain, Lin, and Sahai so far appears to work, but it’s exceedingly slow. The more interesting part of their work is that it uses assumptions that are much less exotic than previous attempts. IND obfuscation can be used to build a lot of other things, so this whole area of research indirectly shows that we can actually build a lot of cryptography based on more robust assumptions than we had previously assumed.
Latest Answers