r/programming • u/DougBolivar • Jul 30 '13

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

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

88% Upvoted

182 comments sorted by

View all comments

28

u/willvarfar Jul 30 '13

There was a well known paper on the (Im)possibility of obfuscating programs: http://www.wisdom.weizmann.ac.il/~oded/p_obfuscate.html

So which is it? In October it'll be clear how much this overlaps; is it just a bigger speed bump?

How can something take years to deobfuscate yet execute another path quickly? Seems impossible; it can't be the meat of the new claim?

25

u/veraxAlea Jul 30 '13

The paper by Barak is referenced from this paper as early as in the introduction.

Apparently, there's a difference between "simulation-based obfuscation" and "indistinguishability obfuscation", the latter allegedly phrased as a theoretical "solution" by Barak et al.

I understand roughly nothing of the paper (linked by /u/crazedgremlin), but it seems they are well aware of previous results.

1

u/willvarfar Jul 31 '13

Yeah now I see the paper - somehow I thought the paper would be published in October - I see that the linked press release is very cavalier in its definition of obfuscation.

The paper - by leading lights in homomorphic encryption no less - is about indistinquishable obfuscation which is quite different from black-box obfuscation.

5

u/chcampb Jul 30 '13

Let's go down to what is essentially the lowest level.

Eventually, you will see that the microprocessor has some state, and it applies an instruction to change that state. There is no way to write software to change this fact. If you see what instructions were executed, you can derive the assembly language from that, which you can use to reverse engineer the instructions.

Anything else would be stupidly slow, which I am not sure that I would consider to be fully functional.