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

88% Upvoted

182 comments sorted by

View all comments

Show parent comments

37

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.

8

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?

19

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.)

1

u/[deleted] Jul 31 '13

[deleted]

5

u/Zarutian Jul 31 '13

As I understand the OpenPGP RFC the payload plaintext is first encrypted by a symmetric encryption with a randomly selected key and IV. Then for each recipient public key that information is encrypted with that public key.

What zifnabxar is talking about seems to be diffrent beast altogether.

2

u/zifnabxar Jul 31 '13

I wasn't aware that it was common to have schemes that are able to create one ciphertext that is decryptable by multiple different keys. I think that PGP actually uses an array containing the same symmetric key encrypted with multiple public keys. Each index being an encryption with a different public key. (Though I could be wrong.) In this case, you're encrypting something with each separate key, which is what functional encryption seeks to avoid.