Provable Obfuscation

An obfuscator O is a "compiler" that transforms your program P into a new program O(P) with the following properties [1]:
1. O(P) has the same functionality as P.
2. O(P) protects any secrets that may be stored inside and used by the program.

Provable obfuscation, if exists, can do wonders in the cryptography world. For example:
- Protection of algorithms and keys in software
- Controlled delegation of authority
- Fully homomorphic public-key encryption
- Digital watermarking
- Making interactive protocols non-interactive

Unfortunately the main provable obfuscation result is a negative one [2]. The following figure shows the security requirements of an obfuscated program O(P):
The obfuscated program should behave like a virtual black box; anything that can be computed from O(P) should be able to be computed by giving oracle access to the program P.

According to current results, it is impossible to achieve the above notion of provable obfuscation on arbitrary programs. So, what can we do best? There are two possible approaches:
1. Restrict ourselves to a weaker form of security
2. Restrict ourselves to special classes of programs (not arbitrary programs)

I prefer to have provable security for small classes of programs instead of having obfuscation techniques for many classes with weaker security. The only positive result that I am aware of is that a point function can be provably securely obfuscated under the random oracle model [1,3].

Here is an example of a point function:
if (input_password == stored_password) {
return true;
} else {
return false;
}

It takes as input the password and outputs true/false. More formally, a point function is a Boolean function that takes the value 1 (true) at exactly one point.

The following shows the common practice to hide password in a system:
if (hash(input_password) == stored_hash) {
return true;
} else {
return false;
}

You can think of the above program as an obfuscated point function where it returns true only if the stored hash value matches the hash of the input password. This can be viewed as a provably secure obfuscation of a point function under the random oracle model. Obfuscation hides the stored password as a hash value. (Hash function acts as a strong one way random permutation. An adversary can only make a dictionary attack to recover the stored password.)



Lynn et. al. [1] extends the above idea to construct provable obfuscation techniques to do more complex access control functionalities. Those who are interested in specific construction techniques are encouraged to read [1] and [3].



[1] Lynn et. al. Positive results and techniques for obfuscation, EUROCRYPT 2004
[2] Barak et. al. On the (im)possibility of obfuscating programs, CRYPTO 2001
[3] Wee, On obfuscating point functions, STOC 2005