Obfuscation: Hiding Secrets in Software

Last week the HEAT-hosted summer school on FHE and multi-linear maps took place. On the final day we learned about indistinguishability obfuscation from the eminent cryptographer Amit Sahai. The talk was entitled 'Obfuscation: Hiding Secrets in Software' and a summary is presented here.

Suppose you want to keep a secret, but some adversary has taken over your brain: whenever you think about the secret, the adversary is able to read it. While this Orwellian nightmare is not realisable for us (at the moment!), in software this happens all the time. This is the fundamental question of obfuscation; i.e., Can we keep a secret from some adversary if all of the functionality is known? Indistinguishability obfuscation is an attempt to realise this.

One early idea on the way to program obfuscation was secure multi-party computation (MPC). The rough idea of secure MPC is to allow each individual of a party to compute some function on everyone's input without anyone learning too much about the input of any other person. In such a situation, an adversary may be one member of the party, or even act as multiple members in order to try to work out something about the input of one of the other party members. In this case, the adversary has a lot of information he can exploit; for true obfuscation, however, we want that nothing at all be revealed to an adversary.

Now we ask the important question, Which programs allow for secrets to be kept? Suppose we have a program with some secret $s$ accepting an integer $x$ as input such that it outputs 1 if $x<s$ and 0 otherwise. By a simple binary search, $s$ can be determined by the adversary. Plausible security requires unknowable queries, so if we are to succeed in obfuscation we need to have a 'virtual black box'.

However, back in 2001, black box obfuscation was suggested and ruled out in the same paper: it cannot be achieved for all programs. The authors go on to describe and define indistinguishability obfuscation (iO) -- obfuscating two programs with the same functionality so the programs are computationally indistinguishable. Interestingly, if P=NP then any circuit can be obfuscated, and so iO cannot produce hardness itself.

This well-known paper was the first construction of iO for NC$^{1}$ circuits. The authors describe a useful possible application: crippleware. Suppose you are a software vendor and have written a program with lots of functionality, and you want to distribute a trial version of the software which is somewhat restricted. In order to block out trial users from using content for which they have not yet paid, one possibility is for you to go through the code and manually remove the blocks of code for which a full licence should be required. In a large program this very cost- and time-inefficient. However, if instead you simply restrict the functionality of the user interface and release an obfuscated version of the program, this version will not have any functionality beyond that which was intended.

Very recently, there have been many attacks on multi-linear maps, many of which rely on obtaining top-level encodings of zero. Because in obfuscation the adversary never has access to encodings of zero, it is resistant to these attacks. Thus the hope remains that obfuscation will not be broken.