# What is this 'mathematical jigsaw puzzles' obfuscation?

You must have heard about it, it all over the on-line newspapers. Some researchers from UCLA claims to have achieved a breakthrough in software obfuscation through 'mathematical jigsaw puzzles'.

Their scientific paper can be found on IACR eprint website.

Can someone sum-up what is really the content of the paper (and does is really worth it) ?

• Why not read the paper? – Antimony Aug 5 '13 at 14:24
• Anyway, I doubt it has any practical applications, but it might be interesting theoretically. – Antimony Aug 5 '13 at 14:37
• @Antimony: I am on it ! But, it's a long one... and I am not a specialist of circuits complexity theory. So, if somebody finish before me and give a perfect explanation, I'll be happy. And, if I finish it before any answer is given, then I will answer to my own question. – perror Aug 5 '13 at 14:37
• – mikeazo Aug 5 '13 at 15:07
• Good shot mikeazo ! I should have looked at Crypto SE... So, it seems that it tries to get the software as close as possible to a black-box analysis. I will try to investigate the practical aspects a bit more in details (implementability and so on). If I find something interesting to say, I'll write an answer here (in a more "Reverse Engineering" way, though). – perror Aug 5 '13 at 15:22

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, lets look at these in turn.

Indistinguishability obfuscation (contributions 1 and 2)
From the paper

It is important to note that unlike simulation-based definitions of obfuscation, it is not immediately clear how useful indistinguishability obfuscators would be. Perhaps the strongest philosophical justification for indistinguishability obfuscators comes from the work of Goldwasser and Rothblum [GR07], who showed that (efficiently computable) indistinguishability obfuscators achieve the notion of Best-Possible Obfuscation [GR07]: Informally, a best-possible obfuscator guarantees that its output hides as much about the input circuit as any circuit of a certain size.

Thus, the main contributions when it comes to Indistinguishability obfuscation of this paper is to show a construction for IO that works on all circuits, then pair that with a few other things to get functional encryption for any circuits.

Note that the usefulness of IOs will only become greater as time goes one. As seen in another paper by some of the same authors and hopefully they will become more practical as new constructions are proposed.

Functional Encryption (contribution 3)
Prior to this work FE has only been possible on small circuits. Using 1 and 2, with some other crypto primitives, the authors were able to build FE on all circuits. That is a very significant result.

What does this mean for Anti-RE
It would appear that by itself, indistinguishability obfuscation means very little for anti-reverse engineering. FE on any circuit, however, could be significant. Here is the reason. FE allows for results of a computation to be in plaintext. Compare this with fully homomorphic encryption (FHE) where results will be encrypted or with Multiparty Comptuation were we require multiple parties (but can have plaintext results). Thus, I could give you a key which would allow you to, say, AES decrypt any data I send to you. You would never know the AES key though. There are techniques that also allow you to hide the function (not just the inputs).

Imagine if you had the ability to allow someone to compute only a specific function(s) on private data that I send you and still get plaintext results. Furthermore, the function is hidden, so they can't reverse engineer the function. That is the contribution of FE, and FE on any circuit is what this work enables.

Practicality
From what I see in the paper, contribution 1 could be practical for real world use, though I am not completely sure. Multilinear maps are pretty inefficient at the moment, but the construction used here is somewhat simplified. Since 2 uses FHE, it isn't practical yet. Since 3 uses 2 and some other heavy-weight crypto, it is also, not practical at the time.

I still wonder should I add a comment on this because my knowledge on the cryptography is extremely limited. The paper on the jigsaw obfuscation uses a term named functional encryption, that means with the private key in hand the obfuscator can design some functions working on the encrypted data. And someone without the private key can use these functions on the encrypted data, but still know nothing about the data.

For example, the obfuscator designs a function plus1 satisfying:

plus1(encrypted(x)) = encrypted(x+1)

the attacker will know that if he uses plus1, he can increase x by 1, but he does not know anything about the value of x.

Now with the jigsaw obfuscation, given a program P with some input a, the obfuscator will encrypt the obfuscated program p as p = encrypt(P), then design a function F with input is some pair (p, a) satisfying:

F(p,a) = decrypt(p)(a) = P(a)

(note that F satisfies the equivalence above but the design of F is not trivial like that), and that means the attacker can always use F and p to get the output P(a), but he does not know anything about P.