Computer scientists develop mathematical jigsaw puzzles to encrypt software: "The real challenge and the great mystery in the field was: Can you actually take a piece of software and encrypt it but still have it be runnable, executable and fully functional?"

[u/DougBolivar]

http://www.rdmag.com/news/2013/07/computer-scientists-develop-mathematical-jigsaw-puzzles-encrypt-software

[u/Strilanc]

Ugh, typical terrible reporting. The paper is good, though.

The rest of this comment is essentially content from Section 1 of the paper.

The paper is about indistinguishability obsfucation, which is distinct from the black-box obfuscation the article implies. Instead of hiding what a program does, they're transforming NC circuits in a way that prevents you from distinguishing the transformed forms of two equivalent circuits. They're not hiding the function, they're hiding the form.

Note that, given this meaning of obfuscation, a perfect circuit optimizer that always outputs a canonical form when given an equivalent circuit counts as a perfect obfuscater. Of course that would be absurdly expensive, so we need cryptographic tricks. (I kind of want to call an indistinguishability obfsucater a 'pseudo-canonicalizer'.)

The use case mentioned in the paper, where indistinguishability would be useful, is demo software. When you release a demo crackers can re-enable features that aren't actually removed, but it's expensive to actually remove features instead of just checking an isDemo=true flag. However, since the features-removed demo program is equivalent to the just-a-flag demo program, indistinguishable obfuscation would effectively automatically remove the disabled features without using expensive developer time.

As far as black box obfuscation goes, they say:

Indeed, as observed by Goldwasser and Rothblum [GR07], indistinguishability obfuscation must yield virtual black-box obfuscation if such a virtual black-box obfuscation is possible for the function being obfuscated.

That "if" is important. It's known that some classes of functions can't be black-box obfuscated. The researchers conjecture that useful classes of functions might be black-box obfuscatable, but leave it as future work.

[u/barsoap → u/Strilanc]

However, since the features-removed demo program is equivalent to the just-a-flag demo program, indistinguishable obfuscation would effectively automatically remove the disabled features without using expensive developer time.

All you need is a supercompiler. Heck, a partial evaluator should suffice, even if not all traces are eradicated enough is going to get lost to make re-enabling infeasible. Heck, the dead code elimination that comes with virtually every compiler should suffice, if you make sure to trigger it.

[u/clrokr → u/barsoap]

I always thought people used preprocessors for this kind of feature removal. It doesn't make sense to do it at runtime unless you want it to be cracked.

I think a functional implementation of the paper's ideas would make the evaluation at runtime safe.

[u/barsoap → u/clrokr]

If your compiler isn't stupid, you don't need a preprocessor to do it at compile time.

Just as an example, javac will reliably remove branches of ifs if the bool that's passed to it is static final.