Send an encrypted question and return answer without decryption

Oke bear with me for a minute.

Once upon a time someone mentioned a hypothetical way where you would send an encrypted question to Google and Google would return an answer without decrypting it. As of lately i'v been searching for this hypothesis thinking there would be something about it on the internet, the problem is i can't find it.

So my question, is this theoretically possible, sending something encrypted and without the receiver knowing what it is return the correct information. Of course i get that when you encrypt every possible question and compare the 2 you could figure out the question and return the answer but i believe this was not how it was hypothetically done.

Has anyone of you ever heard of this? where does it come from?

I'm very sorry I could not provide a link to a paper or anything, I just cannot find anything about it.

• Maybe you are thinking of private information retrieval? Or oblivious transfer? – mikeazo Feb 26 '15 at 13:28
• It sure seems to touch the subject, great read, though i'd have to take a bit more time to fully understand it. but yes i think this is what i was looking for – Vincent Feb 26 '15 at 13:36

Is it theoretically possible? Yes.

Is it practical? Absolutely not.

In your scenario, there are two approaches, but both are pretty much theoretical only.

First, there is fully homomorphic encryption (FHE). This means, you can do computations like addition and multiplication of ciphertexts and get another encrypted message. To actually have some of your usual search algorithms transferred into an "encrypted mode", you would also need things like checking for equality, etc., where you could use other cryptographic primitives, like zero knowledge proofs, OT, secret sharing, ...

But FHE is not practical, because it has a very high constant factor for the overhead. Basically it means, instead of using a modern top-notch computer, you have the performance of a 30 year old one (or older).

Then, there is searchable encryption... Basically it allows the server to produce a result for your search query. But that is not along the lines of a google search but more "find this string in the database". It is not the semantic search, but more a syntactical one, where you search for specific objects, attributes, etc.

But basically, it suffers from the same weakness as FHE: It is not practical. In cryptography, something is efficient if it is polynomial. But for practical usage this is not enough, because constant factors and exponents matter - even if they are theoretical efficient (e.g. $2^{1000}\cdot n$ and $n^{1000}$ are unusable in practice, but they are polynomial)

• Pratical ? IBM have patented methods for FHE issued from Gentry's thesis. Take a look at: github.com/shaih/HElib For the rest Wait and See ! – Robert NACIRI Feb 26 '15 at 14:03
• Yes, IBM and various other companies are working on improving FHE further. And of course they have patents for that. It doesn't mean that it is practical in a sense, that you would actually run it in a scenario, where the user inputs something and expects the output generated on the fly. Or in a scenario with an actual human "user" at all. – tylo Feb 26 '15 at 16:42