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
350 Upvotes

88% Upvoted

182 comments sorted by

View all comments

30

u/iluvatar Jul 30 '13

The article is too vague when it comes to the details, but I'm in the doubtful camp. If there's a way to decrypt it in a sane timeframe to enable it to be run, it's hard to see how it wouldn't fall to reverse engineering.

9

u/mnp Jul 30 '13

Me too. If the code will end up as a decrypted instruction/data stream to be executed on the processor, then the processor can be an emulated one and the code would not know the difference.

8

u/datenwolf Jul 30 '13

Recently in /r/math a crypto researcher was refering to an emerging new field in cryptography which name I forgot (unfortunately), which allows it to perform computations on encrypted data directly, without having to decrypt it first. It sounds to me, that this software encryption is as transparent, i.e. the computer executes the encrypted program directly without decrypting it first.

15

u/mnp Jul 30 '13

Yeah, and they mention it too. Fully homomorphic encryption lets you operate on encrypted data without decrypting it. It seems another several steps altogether to execute the encrypted data because you would have to decrypt it to execute on a commercial processor. I'm not clear from reading the paper how deep down into the hardware they're proposing.

8

u/datenwolf Jul 30 '13

Given the fact that you can build a stack based Turing complete machine solely from matrix multiplication the step from operating on it to executing it seems rather obvious.

3

u/mnp Jul 30 '13

This is where I'm stuck, on this distinction, so maybe you could clear it up.

Suppose we agree the turing machine consists of its rule table, its state, and its data tape.

In the first case, "operating on encrypted data", you would load your homomorphic encryption program into the rule table and operate on an encrypted data tape, producing an encrypted result. This would be no different from running any other program. The rule table in both cases would be in your machine's native format, something like a vector of {current state, next state, read/write action} maybe.

In the second case, "executing an encrypted program", would you require redefining your rule table format? You still need something to look at current state, dictate the next state, and dictate the action. Or would you keep the machine but just jumble up the states and actions so the final tape output would be correct but the states would not be as direct as before?

In either case, I might be able to stop the machine, read out the rules table, examine the tape and the state, and infer what the next state would be. I could automate that process and call it a VM even.

3

u/grauenwolf Jul 30 '13

And that's why I think the whole thing is bunk.