Can Homomorphic Encryption be Practical?
eprint.iacr.org
eprint.iacr.org
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?
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.
"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).
You might want to try wikipedia's explanation: http://en.wikipedia.org/wiki/Homomorphic_encryption
Edit: Someone with more insight came along. This post explains the real issue going on here much better: http://news.ycombinator.com/item?id=2827465 Read that one instead.
If I have a function f and you have some data x, and you want to compute f(x), then without fully homomorphic encryption, either I have to give you my function or you have to give me your data. With fully homomorphic encryption, you can give me your encrypted data and I can use that as input to my function, so that you don't learn what my function is and I don't learn what your data is. I give you the output of the function, and you can decrypt it to learn what f(x) is without learning f.
I think the use case where I want to compute f(x) in an untrusted (eg cloud) environment is probably the real potential use case.
The (slightly odd) book Translucent Databases gives some more use cases, such as working with anonymised statistics.
If someone was trying to be dishonest then they could fake any attribute of f() that you could likely verify.
Not necessarily. For example: you can't fake bitcoin transactions, as each one requires significant amount of comuptation. Basically faking would require exactly the same work (modulo problems with SHA1 itself, but that's another matter).
This is used for other purposes as well: http://en.wikipedia.org/wiki/Proof_of_work
Proof of work techniques are relying on forcing the other party to run a known function in order to prevent various attacks. If the other party can't verify the result they would be no use.
I've blogged about it when it first became possible, in 2009: http://metaphysicaldeveloper.wordpress.com/2009/11/30/you-ca...
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.
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) ?
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/9854ad3cab48983f7c2c5a2258...
Edit: Looking through this one now: 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.
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.
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. :)
Kudos to the researchers as there is valuable information contained.
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.
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.