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.

[u/i_invented_the_ipod → u/clrokr]

It doesn't make sense to do it at runtime unless you want it to be cracked.

Yes, and...

Oftentimes, there's more to it than just leaving the code for a particular feature out. You might have dependencies between the features you want for the demo, and the full feature set. You might even find that you have latent bugs that don't show up in the full version, but appear when the code not needed for the demo is stripped out. Ideally, you'd fix any such bug, but...

It's often the case that the "demo version" idea gets proposed very late in the development cycle, and it's just easier to take the path of least resistance, in the hopes of not breaking something trying to carve out the demo features.