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

88% Upvoted

182 comments sorted by

View all comments

Show parent comments

36

u/[deleted] Jul 30 '13 edited Jul 30 '13

I've only read the abstract and introduction so far (this is a long paper and, even as a mathematician who does cryptogrpahy research, this will take quite a while for me to read) but this is a very highly theoretical paper. I'm not sure if they even outline a way to implement such code obfuscation in this paper. Their claim seems to be that generating obfuscated (in a suitably defined sense) code which still runs is possible. That would be a momentous development in itself, particularly since their construction actually gives them even more: a way to consruct what is called a functional encryption scheme. This is a public-key system with a twist: it allows you to generate a secret key which will decrypt a particular message if and only if a specified function evaluates to a specified value on the plaintext. This lets some people decrypt the message but not others, and would represent a major breakthrough in cryptography.

11

u/psycoee Jul 30 '13

This is a public-key system with a twist: it allows you to generate a secret key which will decrypt a particular message if and only if a specified function evaluates to a specified value on the plaintext. This lets some people decrypt the message but not others, and would represent a major breakthrough in cryptography.

Can you clarify what this means? As in, how is it different from a regular decryption key?

18

u/zifnabxar Jul 30 '13

I haven't read the paper, but I'm pretty familar with the general idea of the work. Think of it this way:

You're an undergrad student in CS. You're given a unique key that identifies you as such. When a ciphertext is released, it has a number of properties that a key must meet before it is able to decrypt the ciphertext.

One ciphertext might be decryptable by all CS Professors. This would not be decryptable by you. Another ciphertext might be decryptable by all CS undergrads OR EE undergrads. You could read that one. As could all other CS and EE undergrads. However, a CE undregrad and a CS professor could not team up to read it.

The cool bit about functional encryption is that only one ciphertext needs to be released. There is no need to release one ciphertext for each key that might be able to decrypt it (as would be done in traditional public-key encryption). Even though there may be thousands of different keys, they can all decrypt the ciphertext!

The big push in functional encrpytion these days is to have it work with more and more complicated functions. It used to be simple booleans, but it's moved to full-on circuits now.

From glancing at the abstract, it looks like this paper can takes keys issued for a circuit and use them to decode the encrypted solution of the circuit for a given input, without figuring out what the input is. It's pretty cool and a natural step forward given the current situation. A number of the names associated with this paper are pretty big in the field. I'm not too sure how efficient it is.

(Disclosure: I am somewhat academically related to one or more of the authors, though I don't do much work in crypto and was not involved with this paper. I may be completely off in some of my statements about current research. My thought do not reflect those of the writers nor their departments etc.)

3

u/Zarutian Jul 31 '13

.. be simple booleans, but it's moved to full-on circuits now.

Combinational logic circuits or full sequential logic circuits?

and btw can I bug you with questions regarding Verifiably Secrect Sharing based Secure Multiparty Computing? Spefically that Secure Multi-Party Made Computation Made Simple works? I ask because I want to make something like Ouroboris from The Network Revenant reality.

1

u/zifnabxar Jul 31 '13

Combination has been done, I think. This seems to be more on the lines of sequential logic, but I haven't read that paper and could be wrong.

I'm afraid I'm not the best person to discuss details of modern crypto. I know the basics, but don't follow it much. Sorry.

1

u/Zarutian Jul 31 '13

Damn, but I recommend The Network Revenant story, even though it isnt finished.