Send an encrypted question and return answer without decryption

Question

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.

Answer 1

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)