Practical consequences of using functional encryption for software obfuscation

Question

I came across this article, which describes a method, developed by UCLA CS professor Amit Sahai et al, for using functional encryption in order to achieve software obfuscation. The paper that the article refers to is available here. Has anyone digested the paper and have more information to share? Are the results as ground breaking as the article suggests?

In particular, does anyone have a clear idea regarding exactly what aspect of an implementation the method will potentially obfuscate? Does it only apply to hardware implementations at the integrated circuit level? Does it apply even if the adversary is able to track and map signals once the chip is turned on? Does it apply to software implementations for generic platforms, even if the adversary has full control over the CPU and internal memory (e.g. in case of emulators)?

Answer 1

Are the results as ground breaking as the article suggests?

This result will prove to be a very important one for theoretical crypto. The analogy to fully homomorphic encryption (mentioned above by Samuel) is useful, since that is another well-known result that was hugely groundbreaking from a theoretical point of view, but even years later the constructions are not what one would consider "practical."

does anyone have a clear idea regarding exactly what aspect of an implementation the method will potentially obfuscate?

The obfuscated program will hide all aspects of the implementation, except for the output. That's the definition of obfuscation. Well, mostly. The most natural definition of obfuscation is impossible to achieve in general. Without getting into too many technical details, this paper shows how to get something weaker called "indistinguishability obfuscation", which is known to be the best possible kind of obfuscation you could hope for in light of the impossibility result. Unfortunately, it's somewhat difficult to interpret exactly what you get from indistinguishability obfuscation. The authors do mention this in their paper.

Does it only apply to hardware implementations at the integrated circuit level?

There's nothing really specific to hardware in this paper. You can obfuscate any program, hardware or software. But perhaps the confusion comes from the fact that, in order to user their obfuscation, you have to express your program as a boolean circuit (of AND, OR, NOT gates), not as a Turing machine or assembly code or C or whatever. This is pretty standard in the theoretical literature, but a source of a lot of the impracticality of these kinds of constructions.

Does it apply even if the adversary is able to track and map signals once the chip is turned on? Does it apply to software implementations for generic platforms, even if the adversary has full control over the CPU and internal memory (e.g. in case of emulators)?

There are no such restrictions on the adversary. Thinking at the software level, the obfuscated program is just a big blob of 1s and 0s that you hand over to the adversary. Now the adversary can do whatever it likes with the blob of data. The security guarantee (more or less) is that the only useful information that the adversary can get out of this blob of data is the ability to execute the program on inputs of its choice. Sure, this covers situations where you imagine the adversary to have full control of the hardware on which the obfuscated program is executing.

Answer 2

Wanted to add some to Mikero's answer.

There are three main contributions of the research

1. A proposed indistinguishability obfuscation for NC1 circuits where the security is based on the so called Multilinear Jigsaw Puzzles (a simplified variant of multilinear maps).

2. Pair the contribution in 1 with Fully Homomorphic Encryption and you get indistinguishability obfuscation for all circuits.

3. Combine 2 with public key encryption and non-interactive zero-knowledge proofs and you functional encryption for all circuits. I believe that prior to this functional encryption for all circuits was not possible.

So, the answer really depends on which contribution you are referring to.

Are the results as ground breaking as the article suggests?

If you are referring to contribution #3, then I think the answer is a definite yes (even if in implementation would still not be practical due to FHE use in #2). The reason for this is that until now, FE for all circuits was not possible. So, this is the first construction of FE for all circuits.

#1 and #2 have the possibility of being fairly ground breaking. Though, as noted by others, we are only beginning to realize what indistinguishability obfuscators can do. This paper presents one application, FE for all circuits. Another paper by some of the same authors uses IO to build deniable encryption. I'd suggest reading that paper too if you are interested in the area.

does anyone have a clear idea regarding exactly what aspect of an implementation the method will potentially obfuscate?

This really depends on what you are talking about. If you are talking about #1 and #2, then we don't really know. To begin, we must understand what an indistinguishability obfuscator is. Say we have $\mathcal{O}$ which is an indistinguishability obfuscator and two (functionally equivalent) circuits $C_1,C_2$ of the same size. An indistinguishability obfuscator says that $\mathcal{O}(C_1)$ is indistinguishable from $\mathcal{O}(C_2)$. Furthermore, it was shown that $\mathcal{O}$ has the property that no $\mathcal{O}'$ (even an inefficient one) makes $C_1$ and $C_2$ more indistinguishable. Notice that all this says is that obfuscated equivalent circuits are equally obfuscated (since they are indistinguishable). And that no other obfuscator can make them more equally obfuscated. This says nothing about the quality of the obfuscation (i.e., can you get the program internals from the obfuscation).

Now, if you are referring to #3, then the story is different. Functional encryption (in the standard sense) is not function (or software) obfuscation. So, #3 does not obfuscate anything if you are talking about the function computed by the functional encryption. Though there are techniques to hide the function that I'm guessing can be combined with this result to any circuit.