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?
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.
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).
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.
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.
My understanding is that fully homomorphic encryption allows proprietary logic to stay hidden by allowing a company to perform its proprietary logic on a customer's data without seeing the data.
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.
In a lot of use cases for this I also need to be able to verify you did apply f too, which may be hard. There is clearly a huge lack of trust here. Thinking of financial service applications like trading.
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).
I'm not familiar with the details of bitcoin, but in that case aren't (some of) the inputs to the function hidden not the function itself.
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.
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.
I don't know. I'm not sure if it's been proven one way or another. Hopefully someone with more insight comes along. I remember Gentry's scheme working this way, but I'm not sure if all fully homomorphic ones do. Some of the partially homomorphic ones don't, I think.
What am I missing? Code is data. Fix a Boolean circuit for a universal interpreter unrolled to whatever depth is needed. Send your program code and its input as the data payload and have it passed to the circuit.
It is really useful for making remote and encrypted dbs, not to mention that you can safely store any data on Amazon EC2, compute on it, and only the producers and the consumers of the input/output will ever know the contents.
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.
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.
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) ?
> 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.
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.
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.
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. :)
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.
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.
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.
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.
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?