4 ms·

A working implementation of fully homomorphic encryption [pdf]

26 points by hadronzoo 16y ago

Bootstrapping technique: http://eprint.iacr.org/2010/145.pdf

hadronzoo 16y ago
Bootstrapping technique: http://eprint.iacr.org/2010/145.pdf http://eprint.iacr.org/2010/145.pdf
davidj 16y ago
If I understand this right, this would mean now you could do all the calculations on your data on a cloud based solution without disclosing the data or results, a huge breakthrough for securing sensitive data on the cloud. Or another example, you could run a Google search and Google would return the results without knowing the results or what you initially searched for. This kind of reminds me of the tor network. On the other side, it would make it impossible to know if your cloud system was infected with spyware because you could never prove what it would be doing. But on the other hand, that could actually be a solution to a larger problem, which would solve the problem of pirated software by limiting crackers the ability to decipher the registration-code algorithm of a software product.
sweis 16y ago
This is a related paper on eprint: http://news.ycombinator.com/item?id=1784602 http://news.ycombinator.com/item?id=1784602
trotsky 16y ago
What is Homomorphic Encryption, and Why Should I Care? http://blogs.teamb.com/craigstuntz/2010/03/18/38566/ http://blogs.teamb.com/craigstuntz/2010/03/18/38566/
- Groxx 16y ago
  I was just going to link to this, but ya beat me to it! It's an interesting article pair, but seems to have stopped rather abruptly for quite a while now...
zitterbewegung 16y ago
Bruce Schneier on homomorphic encryption http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html http://www.schneier.com/blog/archives/2009/07/homomorphic_en... Side note by me: If this is shown to be actually secure then this would be very interesting. Note he states that an efficient algorithm would take 40 years.
partition 16y ago
I have a question about homomorphic encryption and information leakage. Do I have this right: A homomorphic encryption is a function e :: P -> C between groups (P, -) and (C, +), where P is the set of plaintext and C is the set of gibberish and -, + are the respective group operations in either space, such that e is a homomorphism in the group theoretic sense? Because if so, the following basic properties must hold: e(id_P) === id_C e(inv(p)) === inv(e(p)) Suppose you are a malicious cloud services provider and you are manipulating encrypted data. Couldn't you use these group properties to make much more informed observations about the encrypted data without ever having to decrypt it? A very simple example: as a malicious cloud services provider, if you see a bunch of gibberish strings x, y1, y2 ... yn, and it turns out that x + y1 == y1, x + y2 == y2, ... x + yn == yn, wouldn't you at least have a sneaking suspicion, that x is the identity element? And in the situation where you could potentially make very damaging (to the other party) decisions based on this information, it would seem to defeat the purpose of homomorphic encryption. Moreover, recall that the cloud services provider is technically also allowed to run any additional set of calculations using the group operation on the data you give it, not just those you provided. It seems that, in general, even with very unstructured data you could use the properties of homomorphisms to de-anonymize data very easily. How is this issue addressed?
- Groxx 16y ago
  From what I remember from reading an ACM article on it a couple months back, you can also run the operations after they have been encrypted as well, preventing it a bit. I don't remember if there's a way to require encrypted operations, though. In doing this, you could still brute-force operations and watch for statistically-significant results... but you'd have to guess at what valid operations are. Which amounts to the same problem as cracking the encryption in the first place, though it seems to me it would be an attack vector which weakens the encryption as a whole. To a significant degree? Don't know / doubt it. Just don't ask me to explain the math of it. I don't know it, though I plan on studying enough to grasp it. Should take a few years. edit: meh to the above. Now that I've thought about it a bit longer, I do remember a decent chunk of the article dealing with information leakage, and how algorithms would need to be designed to touch as much information as possible (ideally, everything) to prevent leakage. So, it seems a map/reduce setup which combines all datapoints (removing unimportant ones further down the chain, thus hiding their influence) would be valuable.
djcapelis 16y ago
Does anyone know anything about the availability of this implementation? (Before anyone gets excited: For poking at, not production use, being able to use the thing would help me understand their paper better...)

26 points by hadronzoo 16y ago

Bootstrapping technique: http://eprint.iacr.org/2010/145.pdf

hadronzoo 16y ago

Bootstrapping technique: http://eprint.iacr.org/2010/145.pdf http://eprint.iacr.org/2010/145.pdf

davidj 16y ago

If I understand this right, this would mean now you could do all the calculations on your data on a cloud based solution without disclosing the data or results, a huge breakthrough for securing sensitive data on the cloud. Or another example, you could run a Google search and Google would return the results without knowing the results or what you initially searched for. This kind of reminds me of the tor network. On the other side, it would make it impossible to know if your cloud system was infected with spyware because you could never prove what it would be doing. But on the other hand, that could actually be a solution to a larger problem, which would solve the problem of pirated software by limiting crackers the ability to decipher the registration-code algorithm of a software product.

sweis 16y ago

This is a related paper on eprint: http://news.ycombinator.com/item?id=1784602 http://news.ycombinator.com/item?id=1784602

trotsky 16y ago

What is Homomorphic Encryption, and Why Should I Care? http://blogs.teamb.com/craigstuntz/2010/03/18/38566/ http://blogs.teamb.com/craigstuntz/2010/03/18/38566/

Groxx 16y ago
I was just going to link to this, but ya beat me to it! It's an interesting article pair, but seems to have stopped rather abruptly for quite a while now...

zitterbewegung 16y ago

Bruce Schneier on homomorphic encryption http://www.schneier.com/blog/archives/2009/07/homomorphic_enc.html http://www.schneier.com/blog/archives/2009/07/homomorphic_en... Side note by me: If this is shown to be actually secure then this would be very interesting. Note he states that an efficient algorithm would take 40 years.

partition 16y ago

I have a question about homomorphic encryption and information leakage. Do I have this right: A homomorphic encryption is a function e :: P -> C between groups (P, -) and (C, +), where P is the set of plaintext and C is the set of gibberish and -, + are the respective group operations in either space, such that e is a homomorphism in the group theoretic sense? Because if so, the following basic properties must hold: e(id_P) === id_C e(inv(p)) === inv(e(p)) Suppose you are a malicious cloud services provider and you are manipulating encrypted data. Couldn't you use these group properties to make much more informed observations about the encrypted data without ever having to decrypt it? A very simple example: as a malicious cloud services provider, if you see a bunch of gibberish strings x, y1, y2 ... yn, and it turns out that x + y1 == y1, x + y2 == y2, ... x + yn == yn, wouldn't you at least have a sneaking suspicion, that x is the identity element? And in the situation where you could potentially make very damaging (to the other party) decisions based on this information, it would seem to defeat the purpose of homomorphic encryption. Moreover, recall that the cloud services provider is technically also allowed to run any additional set of calculations using the group operation on the data you give it, not just those you provided. It seems that, in general, even with very unstructured data you could use the properties of homomorphisms to de-anonymize data very easily. How is this issue addressed?

Groxx 16y ago
From what I remember from reading an ACM article on it a couple months back, you can also run the operations after they have been encrypted as well, preventing it a bit. I don't remember if there's a way to require encrypted operations, though. In doing this, you could still brute-force operations and watch for statistically-significant results... but you'd have to guess at what valid operations are. Which amounts to the same problem as cracking the encryption in the first place, though it seems to me it would be an attack vector which weakens the encryption as a whole. To a significant degree? Don't know / doubt it. Just don't ask me to explain the math of it. I don't know it, though I plan on studying enough to grasp it. Should take a few years. edit: meh to the above. Now that I've thought about it a bit longer, I do remember a decent chunk of the article dealing with information leakage, and how algorithms would need to be designed to touch as much information as possible (ideally, everything) to prevent leakage. So, it seems a map/reduce setup which combines all datapoints (removing unimportant ones further down the chain, thus hiding their influence) would be valuable.

djcapelis 16y ago

Does anyone know anything about the availability of this implementation? (Before anyone gets excited: For poking at, not production use, being able to use the thing would help me understand their paper better...)