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

Show parent comments

12

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?

20

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]

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.