Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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)?

share|improve this question
3  
The researchers said their mathematical obfuscation mechanism can be used to protect intellectual property by preventing the theft of new algorithms and by hiding the vulnerability a software patch is designed to repair when the patch is distributed. which means all obfuscated software are potential malware. But really, wouldn't that technique make AVs practically irrelevant? I think the article is available here –  rath Jul 30 '13 at 23:30
2  
@rath AVs are practically irrelevant for keeping your computer secure. The only reason for having them is to avoid the accusation of negligence for not having one. –  CodesInChaos Jul 31 '13 at 9:11
    
@CodesInChaos: AVs might be an issue anyway, at least from a commercial point of view, because a significant fraction of ISV consumers would probably never install ISV software on a platform that isn't protected by AV software. However, I am not entirely sure this is an issue, considering that software obfuscation still can't hide certain detectable behavior, such as potentially harmful OS API calls. –  Henrick Hellström Jul 31 '13 at 9:51
4  
There's nothing practical about that paper. Notice the use of multilinear maps and fully homomorphic encryption. I suspect this will only be practical when FHE is also practical. –  Samuel Neves Jul 31 '13 at 10:56
add comment

2 Answers

up vote 9 down vote accepted

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.

share|improve this answer
    
Just to be clear wrt practicality: If obfuscation means expressing the program in terms of AND, OR and NOT, it seems inevitable that it will become extremely inefficient to implement something as simple as an integer multiplication in software, no? –  Henrick Hellström Jul 31 '13 at 21:43
    
To be clear, expressing a program as a boolean circuit is just a prerequisite to obfuscation, and is not meant to impart any security itself (not sure if that's implicit in your comment). Any polynomial-time program (Turing machine) can be encoded as a polynomial-sized circuit. Of course there is a big (but poly) overhead, so it depends on what you mean by "extremely inefficient" (theoretician's definition or something informal). For the particular case of multiplying integers, that's something that computer engineers have been doing for ages: en.wikipedia.org/wiki/Binary_multiplier –  Mikero Jul 31 '13 at 21:48
    
I meant "something informal", since even a polynomial overhead in some cases might be practically prohibitive. For instance, if you try to implement RSA 2048 using boolean gates for e.g. x86 or ARM and use it in a SSL/TLS implementation, the remote peer will time out and disconnect before you stand a chance to complete the handshake. –  Henrick Hellström Jul 31 '13 at 21:55
    
The constants involved in FHE mean it is not even remotely practical. Also, obfuscation will never been practical in situations where maximum performance is critical since there is an inherent penalty to not being able to understand the code you're executing (branch misprediction, cache misses, etc.) It's conceivable that advances in obfsucation may someday let it be executed within a small factor of native performance though (Say 100x slowdown), in which case it would see potential applications. –  Antimony Aug 6 '13 at 3:17
    
What does this mean , expressing program as Turing Machine ? –  sashank Aug 7 '13 at 1:32
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.