7 ms·

Can Homomorphic Encryption be Practical?

73 points by adulau 15y ago

robmay 15y ago
I sat through a recent presentation about this at M.I.T. While it's a long way from practical implementation, it does seem like it is at least feasible that we will get there.
- djcapelis 15y ago
  I don't suppose you feel like sharing your reasoning behind this speculation, do you? There's some fundamentally annoying information theory involved in constructing an actual secure scheme. Gentry ran into some issues and I think the frustrating aspects of his scheme aren't particularly well understood. Oh, and as an explantion, I voted you down because you're chiming in merely to state that you think the answer is that a fully homomorphic scheme is practical without discussing any of your reasoning for your claim or a basis... that didn't rise to the level where it seemed like it was a contribution to the discussion anymore than a comment that said "Yep, this is a really hard problem" would.
  - seats 15y ago
    djcapelis, Seems empirically like you are the most knowledgeable on the thread on this topic. Maybe you can help me understand the current state of this research a little better. I understand that there are reference implementations that show fully homomorphic encryption in action but there is an efficiency issue, but just how severe is the inefficiency? To me practicality comes down to whether or not any application given current algorithms is worth that inefficiency and if it works at all it seems like there must be some edge use case where even the most severely inefficient implementation still meets a need. So two questions for you- What is the definition of 'practicality' at this point (i.e. how efficient does this need to be)? What is the current efficiency (and how is it being measured, big O notation per key length?, something else) ?
    - djcapelis 15y ago
      > Seems empirically like you are the most knowledgeable on the thread on this topic A disappointing conclusion. Welcome to HN on a weekend I suppose. > What is the definition of 'practicality' at this point (i.e. how efficient does this need to be)? Hard to tell, but probably a good goal for practicality would be looking at the number of computations it takes to do an operation on ciphertext needs to be a reasonably low enough number that it actually makes sense to put it in the cloud. If it takes 10,000 computers to do the work of one, then it doesn't make much sense to use the cloud instead of just buying a machine. The only real answer to your question is to look at the relative costs of buying a machine vs. using the cloud and figure out how big of a factor difference that is, that's going to be slightly different for every org, but not likely to be larger than say... maybe 5-10x? So if you accept that as being a reasonable benchmark, then you'd want to see a homomorphic scheme that allows 5-10 computers using homomorphic encryption operations to keep up with one doing operations on plaintext. Maybe there's some absurd circumstances where 100x is still practical, but there's obviously a limit. > What is the current efficiency (and how is it being measured, big O notation per key length?, something else) ? Not entirely sure what the current state of the art is. I haven't really checked on this since reading Gentry's thesis. I understand there were some advanced and some simplifications since then, but I believe we started out in the realm of it being about 10^6x times more complex to do homomorphic operations than plaintext operations with Gentry's first scheme that showed it was even possible. So even if this has gone down quite a bit, we've got a long way to go before we're talking only a 10x - 100x hit. Here's what I found with a quick Google, but I didn't quite find the numbers I could translate into anything reasonable, so maybe you can make sense of it: http://eurocrypt2010rump.cr.yp.to/9854ad3cab48983f7c2c5a2258e27717.pdf http://eurocrypt2010rump.cr.yp.to/9854ad3cab48983f7c2c5a2258... Edit: Looking through this one now: http://eprint.iacr.org/2010/520.pdf http://eprint.iacr.org/2010/520.pdf Editx2: Oh, I suppose the real problem I should have mentioned is the more complex things you want to do, the worse it gets and "complex" here means "how many multiplies" which for a lot of things people want to do is "a lot." So for each scheme, the overhead changes somewhat wildly based on how you encode what you want to do into adds and multiples, or whatever basic blocks it's using.
      - seats 15y ago
dollarsigns 15y ago
@arash/DropBox: you may want to take a look at this. (This can address the issue of digests in context of distinct keys.)
endergen 15y ago
I'd love to have some explain a few simple walkthroughs of why it's not doable. For instance couldn't you do you distributed text search by scrambling text content and then doing search on scrambled search terms? Or is that not secure due to being able to infer text content by analyzing the frequency of certain sequences(Certain letters/phrases will show up.) Anyone? In general there must be classes of symbolic manipulation that is jus abstract pattern matching that doesn't have to unencrypted to work. What are some concrete examples of it just not working.
- jerf 15y ago
  A simple layman/lossy walkthrough of what homomorphic encryption is is on the edge of feasible, though I don't know of a good one beyond the mere definition. A walkthrough of why homomorphic encryption may or may not ever be efficient probably isn't; as this implies, it's an open problem on the cutting edge of research, so metaphorically the ground is rough and the jungle is still wild. We don't have a paved path with convenient rest stops for that yet.
- djcapelis 15y ago
  The problems with the scheme you presented aside, you've misunderstood the problem. The goal isn't just to be able to do limited things like searching or other select things, the goal of a fully homomorphic cryptosystem is to allow any computation on encrypted data. Existing relatively feasible partially homomorphic schemes exist that allow you to do some things on encrypted data, like adds for instance. Search is also possible, I think. But neither have much to do with whether a fully homomorphic scheme is practical.
  - endergen 15y ago
    Ha, yes looking at my text search example again, it is totally illogical.
- deleted 15y ago
  [deleted]
fragsworth 15y ago
I'm kind of new to this, but here's my understanding of this idea - "Fully Homomorphic Encryption" allows a computer to run an encrypted program without knowing what goes on inside. It's like a true black box, without any feasible way of accessing the internal components. I assume there are also ways of sending unencrypted inputs into the black box, and receiving unencrypted outputs, otherwise it would be relatively useless. If I understand it correctly, then I see at least one application in web games. You could have the client run the entire game, by sending user inputs into the black box, and then later saving their game by sending the black box back to the server. This would allow cheat-proof gaming without any server validation required (until saving).
- djcapelis 15y ago
  You're actually looking at it backwards. The data is the black box. The operations being conducted on it are sometimes unknown by the system conducting them, but this isn't a requirement for homomorphic encryption or necessarily the point. You might want to try wikipedia's explanation: http://en.wikipedia.org/wiki/Homomorphic_encryption http://en.wikipedia.org/wiki/Homomorphic_encryption
  - fragsworth 15y ago
    The paper mentioned that the functions in the financing applications might be proprietary, and it would be the point in their case to keep this logic hidden.
    - djcapelis 15y ago
      Yes, many homomorphic schemes seem to enable privacy of the operations being conducted as well as the data being operated on, but that isn't what defines a fully homomorphic scheme.
      - andrewcooke 15y ago
        but it is a natural consequence of one, right? [i am asking; it seems like it might be, but i have no technical insight]
WordSkill 15y ago
I prefer Homophobic Encryption: you obscure what you're saying by speaking in an extremely effeminate voice.
mvzink 15y ago
tl;dr "Maybe, but somewhat homomorphic encryption definitely can be!"
d0ne 15y ago
We've looked into this at Social Fortress and while Homomorphic Encryption could have interesting uses there are more practical approaches for the enterprise in the use cases presented in this paper. Kudos to the researchers as there is valuable information contained.
robinhouston 15y ago
Here is a question that’s puzzling me. Since this thread has already dropped off the front page, and it probably won’t be seen by many people, I’ve also posted it at http://bosker.wordpress.com/2011/07/31/something-i-don’t-understand-about-homomorphic-encryption/ http://bosker.wordpress.com/2011/07/31/something-i-don’t-und... The homomorphic encryption techniques seem to allow the computation of arbitrary polynomials over various finite rings, and – at least in everything I’ve read – it’s always treated as obvious that this is equivalent to allowing arbitrary computations. Is that actually true? If so, is it really obvious? I’d love some enlightenment here. A related source of confusion is that clearly any encryption scheme that <em>actually</em> supported arbitrary computations on encrypted values would be hopelessly insecure. For example, suppose you have encrypted a ten-character ascii password. I then run the function that extracts the first character. The result I get is still encrypted, but since there are only 128 possible values for an ascii character, I can encrypt each of these values and compare the result to the result of my computation. (I can do this because I can always encrypt any data of my choice, just by running a constant-valued function inside the encryption.) Then I do the same for the second character, and so on, till I have your complete password. Encryption fail! The only reasonable conclusion I can draw from this is that fully homomorphic encryption does not really permit arbitrary computations on the encrypted data. In that case, 1. Why do people keep saying it does? 2. What is the class of computations that are in fact permitted? Is it just the evaluation of polynomials? Anyone?
- nhaehnle 15y ago
  You are assuming that encrypting is a bijection, i.e. that for every plaintext, there is only one possible ciphertext. One of the first things you learn in a public key cryptography is that you have to add random bits in the computation of the ciphertext, either via simple random padding (in the case of RSA) or via some more involved steps (in the case of cyclic group-based cryptography). I don't know much about homomorphic encryption (the concept has always seemed contrived to me - if you don't trust your cloud provider, hosting your own servers will always be much more efficient), but I assume they use similar tricks. As for the thing about polynomials: it should be obvious that any polynomial-time computation on an input of a fixed size can be expressed by a DAG of logic gates. Logic gates can in turn be represented by simple polynomials over the field F_2 = { 0, 1 }, and the composition of gates is then simply the composition of polynomials. Since we're talking about fixed-size inputs, this does not really capture the full Turing machine model. However, since all practical encryption schemes can be broken via brute force in exponential time anyway, it only really makes sense to worry about implementing polynomial-time computations in the context of homomorphic encryption.
deleted 15y ago
[deleted]

73 points by adulau 15y ago

I sat through a recent presentation about this at M.I.T. While it's a long way from practical implementation, it does seem like it is at least feasible that we will get there.

djcapelis 15y ago
I don't suppose you feel like sharing your reasoning behind this speculation, do you? There's some fundamentally annoying information theory involved in constructing an actual secure scheme. Gentry ran into some issues and I think the frustrating aspects of his scheme aren't particularly well understood. Oh, and as an explantion, I voted you down because you're chiming in merely to state that you think the answer is that a fully homomorphic scheme is practical without discussing any of your reasoning for your claim or a basis... that didn't rise to the level where it seemed like it was a contribution to the discussion anymore than a comment that said "Yep, this is a really hard problem" would.
- seats 15y ago
  djcapelis, Seems empirically like you are the most knowledgeable on the thread on this topic. Maybe you can help me understand the current state of this research a little better. I understand that there are reference implementations that show fully homomorphic encryption in action but there is an efficiency issue, but just how severe is the inefficiency? To me practicality comes down to whether or not any application given current algorithms is worth that inefficiency and if it works at all it seems like there must be some edge use case where even the most severely inefficient implementation still meets a need. So two questions for you- What is the definition of 'practicality' at this point (i.e. how efficient does this need to be)? What is the current efficiency (and how is it being measured, big O notation per key length?, something else) ?
  - djcapelis 15y ago
    > Seems empirically like you are the most knowledgeable on the thread on this topic A disappointing conclusion. Welcome to HN on a weekend I suppose. > What is the definition of 'practicality' at this point (i.e. how efficient does this need to be)? Hard to tell, but probably a good goal for practicality would be looking at the number of computations it takes to do an operation on ciphertext needs to be a reasonably low enough number that it actually makes sense to put it in the cloud. If it takes 10,000 computers to do the work of one, then it doesn't make much sense to use the cloud instead of just buying a machine. The only real answer to your question is to look at the relative costs of buying a machine vs. using the cloud and figure out how big of a factor difference that is, that's going to be slightly different for every org, but not likely to be larger than say... maybe 5-10x? So if you accept that as being a reasonable benchmark, then you'd want to see a homomorphic scheme that allows 5-10 computers using homomorphic encryption operations to keep up with one doing operations on plaintext. Maybe there's some absurd circumstances where 100x is still practical, but there's obviously a limit. > What is the current efficiency (and how is it being measured, big O notation per key length?, something else) ? Not entirely sure what the current state of the art is. I haven't really checked on this since reading Gentry's thesis. I understand there were some advanced and some simplifications since then, but I believe we started out in the realm of it being about 10^6x times more complex to do homomorphic operations than plaintext operations with Gentry's first scheme that showed it was even possible. So even if this has gone down quite a bit, we've got a long way to go before we're talking only a 10x - 100x hit. Here's what I found with a quick Google, but I didn't quite find the numbers I could translate into anything reasonable, so maybe you can make sense of it: http://eurocrypt2010rump.cr.yp.to/9854ad3cab48983f7c2c5a2258e27717.pdf http://eurocrypt2010rump.cr.yp.to/9854ad3cab48983f7c2c5a2258... Edit: Looking through this one now: http://eprint.iacr.org/2010/520.pdf http://eprint.iacr.org/2010/520.pdf Editx2: Oh, I suppose the real problem I should have mentioned is the more complex things you want to do, the worse it gets and "complex" here means "how many multiplies" which for a lot of things people want to do is "a lot." So for each scheme, the overhead changes somewhat wildly based on how you encode what you want to do into adds and multiples, or whatever basic blocks it's using.
    - seats 15y ago

dollarsigns 15y ago

@arash/DropBox: you may want to take a look at this. (This can address the issue of digests in context of distinct keys.)

endergen 15y ago

I'd love to have some explain a few simple walkthroughs of why it's not doable. For instance couldn't you do you distributed text search by scrambling text content and then doing search on scrambled search terms? Or is that not secure due to being able to infer text content by analyzing the frequency of certain sequences(Certain letters/phrases will show up.) Anyone? In general there must be classes of symbolic manipulation that is jus abstract pattern matching that doesn't have to unencrypted to work. What are some concrete examples of it just not working.

jerf 15y ago
A simple layman/lossy walkthrough of what homomorphic encryption is is on the edge of feasible, though I don't know of a good one beyond the mere definition. A walkthrough of why homomorphic encryption may or may not ever be efficient probably isn't; as this implies, it's an open problem on the cutting edge of research, so metaphorically the ground is rough and the jungle is still wild. We don't have a paved path with convenient rest stops for that yet.
djcapelis 15y ago
The problems with the scheme you presented aside, you've misunderstood the problem. The goal isn't just to be able to do limited things like searching or other select things, the goal of a fully homomorphic cryptosystem is to allow any computation on encrypted data. Existing relatively feasible partially homomorphic schemes exist that allow you to do some things on encrypted data, like adds for instance. Search is also possible, I think. But neither have much to do with whether a fully homomorphic scheme is practical.
- endergen 15y ago
  Ha, yes looking at my text search example again, it is totally illogical.
deleted 15y ago
[deleted]

fragsworth 15y ago

I'm kind of new to this, but here's my understanding of this idea - "Fully Homomorphic Encryption" allows a computer to run an encrypted program without knowing what goes on inside. It's like a true black box, without any feasible way of accessing the internal components. I assume there are also ways of sending unencrypted inputs into the black box, and receiving unencrypted outputs, otherwise it would be relatively useless. If I understand it correctly, then I see at least one application in web games. You could have the client run the entire game, by sending user inputs into the black box, and then later saving their game by sending the black box back to the server. This would allow cheat-proof gaming without any server validation required (until saving).

djcapelis 15y ago
You're actually looking at it backwards. The data is the black box. The operations being conducted on it are sometimes unknown by the system conducting them, but this isn't a requirement for homomorphic encryption or necessarily the point. You might want to try wikipedia's explanation: http://en.wikipedia.org/wiki/Homomorphic_encryption http://en.wikipedia.org/wiki/Homomorphic_encryption
- fragsworth 15y ago
  The paper mentioned that the functions in the financing applications might be proprietary, and it would be the point in their case to keep this logic hidden.
  - djcapelis 15y ago
    Yes, many homomorphic schemes seem to enable privacy of the operations being conducted as well as the data being operated on, but that isn't what defines a fully homomorphic scheme.
    - andrewcooke 15y ago
      but it is a natural consequence of one, right? [i am asking; it seems like it might be, but i have no technical insight]

WordSkill 15y ago

I prefer Homophobic Encryption: you obscure what you're saying by speaking in an extremely effeminate voice.

mvzink 15y ago

tl;dr "Maybe, but somewhat homomorphic encryption definitely can be!"

d0ne 15y ago

We've looked into this at Social Fortress and while Homomorphic Encryption could have interesting uses there are more practical approaches for the enterprise in the use cases presented in this paper. Kudos to the researchers as there is valuable information contained.

robinhouston 15y ago

Here is a question that’s puzzling me. Since this thread has already dropped off the front page, and it probably won’t be seen by many people, I’ve also posted it at http://bosker.wordpress.com/2011/07/31/something-i-don’t-understand-about-homomorphic-encryption/ http://bosker.wordpress.com/2011/07/31/something-i-don’t-und... The homomorphic encryption techniques seem to allow the computation of arbitrary polynomials over various finite rings, and – at least in everything I’ve read – it’s always treated as obvious that this is equivalent to allowing arbitrary computations. Is that actually true? If so, is it really obvious? I’d love some enlightenment here. A related source of confusion is that clearly any encryption scheme that <em>actually</em> supported arbitrary computations on encrypted values would be hopelessly insecure. For example, suppose you have encrypted a ten-character ascii password. I then run the function that extracts the first character. The result I get is still encrypted, but since there are only 128 possible values for an ascii character, I can encrypt each of these values and compare the result to the result of my computation. (I can do this because I can always encrypt any data of my choice, just by running a constant-valued function inside the encryption.) Then I do the same for the second character, and so on, till I have your complete password. Encryption fail! The only reasonable conclusion I can draw from this is that fully homomorphic encryption does not really permit arbitrary computations on the encrypted data. In that case, 1. Why do people keep saying it does? 2. What is the class of computations that are in fact permitted? Is it just the evaluation of polynomials? Anyone?

nhaehnle 15y ago
You are assuming that encrypting is a bijection, i.e. that for every plaintext, there is only one possible ciphertext. One of the first things you learn in a public key cryptography is that you have to add random bits in the computation of the ciphertext, either via simple random padding (in the case of RSA) or via some more involved steps (in the case of cyclic group-based cryptography). I don't know much about homomorphic encryption (the concept has always seemed contrived to me - if you don't trust your cloud provider, hosting your own servers will always be much more efficient), but I assume they use similar tricks. As for the thing about polynomials: it should be obvious that any polynomial-time computation on an input of a fixed size can be expressed by a DAG of logic gates. Logic gates can in turn be represented by simple polynomials over the field F_2 = { 0, 1 }, and the composition of gates is then simply the composition of polynomials. Since we're talking about fixed-size inputs, this does not really capture the full Turing machine model. However, since all practical encryption schemes can be broken via brute force in exponential time anyway, it only really makes sense to worry about implementing polynomial-time computations in the context of homomorphic encryption.

deleted 15y ago

[deleted]