5 ms·

Cryptographic Problem Solved (IBM and "fully homomorphic encryption")

mooism2 17y ago
What does this article add that we did not already know?
- michael_dorfman 17y ago
  That depends on who "we" are, I suppose. I hadn't heard of Gentry's work with the "ideal lattice" before, and a quick search of Hacker News showed no prior discussion. Is this old news?
  - xyanms 17y ago
    http://news.ycombinator.com/item?id=657859 http://news.ycombinator.com/item?id=657859
    - michael_dorfman 17y ago
      Thanks-- I must have missed that the first time around. (Not completely surprising, given the low number of upvotes/comments...)
iamwil 17y ago
I don't understand what kinds of analysis one can do. Following the old link, I downloaded the paper. It mentions in the abstract that it "allows one to evaluate circuits over encrypted data without being able to decrypt". What are circuits in encryption parlance?
- dave_au 17y ago
  IIRC, you can do anything in NC1. http://en.wikipedia.org/wiki/NC_(complexity) http://en.wikipedia.org/wiki/NC_(complexity)
sp332 17y ago
"Fully homomorphic encryption is a bit like enabling a layperson to perform flawless neurosurgery while blindfolded, and without later remembering the episode." Wasn't that a Star Trek episode?
- sown 17y ago
  I can only think of this one: http://memory-alpha.org/en/wiki/Spock%27s_Brain_(episode) http://memory-alpha.org/en/wiki/Spock%27s_Brain_(episode)
  - deleted 17y ago
    [deleted]
rjurney 17y ago
Can someone please explain what this really means? I don't understand. I want to.
- 10ren 17y ago
  I'm guessing; hopefully my betters will correct me. A homomorphism is a mapping which preserves the structure of the original, where structure means the relationship between different parts. For example, x + y = z is a relationship between integers, that is preserved by map(i) = -i. For instance, 2 + 3 = 5, and -2 + -3 = -5. BTW: the more common term isomorphism is a special case of homomorphism, in which you can always do the reverse mapping (technically, an isomorphism is a bijective homomorphism). Because it seems pointless to encrypt something if you can't decrypt it, I think the homomorphism in the article is actually an isomorphism. I think they say "homomorphism" because that is the specific aspect of the breakthrough. Now, it seems that if you encrypt something in a way that preserves structure, it's not going to be very good encryption! Really excellent encryption seems more likely to look like a one-time pad. A one-time pad is when you have a book of unique random numbers, and you encrypt the message by using the message as an index into the book. For example, you can convert the string "hello world" into a number, and use that number as an index into the (very long) book, to find what unique number it refers to. You can then send that unique number to someone else who has the same book - they look it up backwards and get your message out. The encrypted message has no structural relationship to the unencrypted message. This is just one example of absence of structural relationship. What these researchers claim is a way to encrypt a message in an effective way, which also preserves structure. Seems impossible, doesn't it? OK, so what's the point? If you have preserved structure, then you can use tools that analyze structure, such as spam filtering. I tend to think that having the information about whether a message matches spam or not gives you an awful lot of information about the message... counter to the goal of encryption. So I'm withholding judgment... but I suspect that if they have solved this problem, they have done it partly by redefining the nature of the problem in a clever way.
  - jerf 17y ago
    I'm assuming that your spam analysis algorithm will result in a "yes/no" answer that is also encrypted. You can return this value to the originating party, having spent your cycles on computing the answer, but you still don't know what the answer is, only the decrypter does. That said, I'm still not sure how well this could possible seal off the computation from the data. Even if I encrypt a "yes/no" answer, can't I still return either an empty string for "spam", and a long, long string for "not spam". I very much look forward to a decent description of the actual process from someone who has chewed on the original paper for a while, and can process it down from "PhD in encryption" to "bachelors in comp sci + personal study" with minimal fidelity loss.
johnwatson11218 17y ago
I wonder if this could be used to write business apps where you want to work with private information but not actually have access to the info? I know many places have huge databases with personal info, like name, address, ssn etc. What if that info could be worked with in an encrypted manner. Like writing an app to sum up invoices without actually having access to the unencrypted data. If this discovery allows this type of thing I think it will be huge.
- sweis 17y ago
  Yes, there are many constructions for computing over private data that use homomorphic encryption. For example, Paillier's cryptosystem, which supports addition of ciphertexts, has been a building block in many voting protocols. You can also do things like with homomorphic encryption like private set intersections -- meaning that two people could see what's in the intersection of their private sets without revealing anything outside the intersection. Gentry's work is still a long way away from being practical, but is an exciting theoretical result nonetheless.
timf 17y ago
This is a really cool technology but the the implementation needs to get just a little faster: "In the case of a Google search, for instance, performing the process with encrypted keywords would multiply the necessary computing time by around 1 trillion, Gentry estimates" http://www.forbes.com/forbes/2009/0713/breakthroughs-privacy-super-secret-encryption.html http://www.forbes.com/forbes/2009/0713/breakthroughs-privacy...

What does this article add that we did not already know?

michael_dorfman 17y ago
That depends on who "we" are, I suppose. I hadn't heard of Gentry's work with the "ideal lattice" before, and a quick search of Hacker News showed no prior discussion. Is this old news?
- xyanms 17y ago
  http://news.ycombinator.com/item?id=657859 http://news.ycombinator.com/item?id=657859
  - michael_dorfman 17y ago
    Thanks-- I must have missed that the first time around. (Not completely surprising, given the low number of upvotes/comments...)

I don't understand what kinds of analysis one can do. Following the old link, I downloaded the paper. It mentions in the abstract that it "allows one to evaluate circuits over encrypted data without being able to decrypt". What are circuits in encryption parlance?

dave_au 17y ago
IIRC, you can do anything in NC1. http://en.wikipedia.org/wiki/NC_(complexity) http://en.wikipedia.org/wiki/NC_(complexity)

sp332 17y ago

"Fully homomorphic encryption is a bit like enabling a layperson to perform flawless neurosurgery while blindfolded, and without later remembering the episode." Wasn't that a Star Trek episode?

sown 17y ago
I can only think of this one: http://memory-alpha.org/en/wiki/Spock%27s_Brain_(episode) http://memory-alpha.org/en/wiki/Spock%27s_Brain_(episode)
- deleted 17y ago
  [deleted]

rjurney 17y ago

Can someone please explain what this really means? I don't understand. I want to.

10ren 17y ago
I'm guessing; hopefully my betters will correct me. A homomorphism is a mapping which preserves the structure of the original, where structure means the relationship between different parts. For example, x + y = z is a relationship between integers, that is preserved by map(i) = -i. For instance, 2 + 3 = 5, and -2 + -3 = -5. BTW: the more common term isomorphism is a special case of homomorphism, in which you can always do the reverse mapping (technically, an isomorphism is a bijective homomorphism). Because it seems pointless to encrypt something if you can't decrypt it, I think the homomorphism in the article is actually an isomorphism. I think they say "homomorphism" because that is the specific aspect of the breakthrough. Now, it seems that if you encrypt something in a way that preserves structure, it's not going to be very good encryption! Really excellent encryption seems more likely to look like a one-time pad. A one-time pad is when you have a book of unique random numbers, and you encrypt the message by using the message as an index into the book. For example, you can convert the string "hello world" into a number, and use that number as an index into the (very long) book, to find what unique number it refers to. You can then send that unique number to someone else who has the same book - they look it up backwards and get your message out. The encrypted message has no structural relationship to the unencrypted message. This is just one example of absence of structural relationship. What these researchers claim is a way to encrypt a message in an effective way, which also preserves structure. Seems impossible, doesn't it? OK, so what's the point? If you have preserved structure, then you can use tools that analyze structure, such as spam filtering. I tend to think that having the information about whether a message matches spam or not gives you an awful lot of information about the message... counter to the goal of encryption. So I'm withholding judgment... but I suspect that if they have solved this problem, they have done it partly by redefining the nature of the problem in a clever way.
- jerf 17y ago
  I'm assuming that your spam analysis algorithm will result in a "yes/no" answer that is also encrypted. You can return this value to the originating party, having spent your cycles on computing the answer, but you still don't know what the answer is, only the decrypter does. That said, I'm still not sure how well this could possible seal off the computation from the data. Even if I encrypt a "yes/no" answer, can't I still return either an empty string for "spam", and a long, long string for "not spam". I very much look forward to a decent description of the actual process from someone who has chewed on the original paper for a while, and can process it down from "PhD in encryption" to "bachelors in comp sci + personal study" with minimal fidelity loss.

johnwatson11218 17y ago

I wonder if this could be used to write business apps where you want to work with private information but not actually have access to the info? I know many places have huge databases with personal info, like name, address, ssn etc. What if that info could be worked with in an encrypted manner. Like writing an app to sum up invoices without actually having access to the unencrypted data. If this discovery allows this type of thing I think it will be huge.

sweis 17y ago
Yes, there are many constructions for computing over private data that use homomorphic encryption. For example, Paillier's cryptosystem, which supports addition of ciphertexts, has been a building block in many voting protocols. You can also do things like with homomorphic encryption like private set intersections -- meaning that two people could see what's in the intersection of their private sets without revealing anything outside the intersection. Gentry's work is still a long way away from being practical, but is an exciting theoretical result nonetheless.

timf 17y ago

This is a really cool technology but the the implementation needs to get just a little faster: "In the case of a Google search, for instance, performing the process with encrypted keywords would multiply the necessary computing time by around 1 trillion, Gentry estimates" http://www.forbes.com/forbes/2009/0713/breakthroughs-privacy-super-secret-encryption.html http://www.forbes.com/forbes/2009/0713/breakthroughs-privacy...