5 ms·

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

by 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
      Maybe a slow night on HN, but still you were on top of all the answers, so it was worth it to me to get your take. Thanks for the answer. When talking about edge cases I could come up with ones that don't involve the cloud. And in those cases maybe I don't need to replicate a server, but instead I just need to represent a very small amount of data in an encrypted form that can be operated on homomorphically. While I don't have a fleshed out idea on how to apply it, the one area that I'm interested in thinking about homomorphic encryption being applied is POS financial transactions. My gut (and this is just a gut, not backed by in depth thought by any means) is that homomorphic encryption as a building a block could allow you to design a secure and significantly better replacement for the existing credit card (or even chip and pin) system.
      - djcapelis 15y ago
        It's kind of an interesting thing to try and think through. I think emily37's post above brings up one of the more motivating usecases that's going to be much more forgiving when it comes to practicality, which is allowing someone who doesn't want to reveal how they do math on the data and someone else who doesn't want to reveal the data get together and make answers. As for POS systems, I feel like public key is going to be far more applicable than homomorphic is for the usecases that make sense there. But I definitely could be missing something. :)

by 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
    Maybe a slow night on HN, but still you were on top of all the answers, so it was worth it to me to get your take. Thanks for the answer. When talking about edge cases I could come up with ones that don't involve the cloud. And in those cases maybe I don't need to replicate a server, but instead I just need to represent a very small amount of data in an encrypted form that can be operated on homomorphically. While I don't have a fleshed out idea on how to apply it, the one area that I'm interested in thinking about homomorphic encryption being applied is POS financial transactions. My gut (and this is just a gut, not backed by in depth thought by any means) is that homomorphic encryption as a building a block could allow you to design a secure and significantly better replacement for the existing credit card (or even chip and pin) system.
    - djcapelis 15y ago
      It's kind of an interesting thing to try and think through. I think emily37's post above brings up one of the more motivating usecases that's going to be much more forgiving when it comes to practicality, which is allowing someone who doesn't want to reveal how they do math on the data and someone else who doesn't want to reveal the data get together and make answers. As for POS systems, I feel like public key is going to be far more applicable than homomorphic is for the usecases that make sense there. But I definitely could be missing something. :)