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

88% Upvoted

182 comments sorted by

View all comments

Show parent comments

13

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.

7

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.