Comment by BillyMaize
12 years ago
>In theory, fully homomorphic encryption could allow the best of both worlds above. I completely encrypt my data on my machine --- nobody else has the key --- then send it into the cloud where cloud companies can do operations for me like searching, sorting, filtering, etc, all without ever decrypting the data or learning what it is.
Can you explain this to me? I don't understand how you can search encrypted data.
It's mind-boggling, but possible. Here's the wikipedia link: http://en.wikipedia.org/wiki/Homomorphic_encryption
The idea is this: I encrypt my data and give it to the cloud. I also encrypt the algorithm I want the cloud to use. In this case, it could be a search algorithm with the search query hardcoded. Right now, it would have to be encoded as a circuit and then encrpyted from there into a different circuit.
The cloud runs my encrypted data through this "transformed" circuit, yielding some encrypted output. The cloud tells me the output. I then decrypt it with my original key.
It's crazy that this works (longstanding open problem solved in 2005 or 06 I think). The name "homomorphic" comes from functions f, like homomorphisms, in which "order doesn't matter":
Hope that makes some sense.
Ah yes now it seems obvious, thanks.
You don't need full homomorphic encryption to do encrypted search, look up PKES systems, there's tons of papers on it now (http://crypto.stanford.edu/~dabo/abstracts/encsearch.html). It's possible to encrypted keyword search with trapdoor functions in such a way that the server can't learn anything about what you're searching on, nor what is stored.
Are you aware of any vaguely practical systems for a variant of keyword search that just returns whether the keyword was found (e.g. 1 for found, 0 for not found) but with the added requirement that the result must itself be encrypted? I suspect it degenerates to fully homomorphic encryption though.
By result itself, you mean the boolean 1/0 about whether it was found? Yes, I am aware of one I saw some time ago that had additional guarantees, I don't know how practical it was though, but it'll take some searching to find.