Earlier quoted context omitted.
Homomorphically encrypted services don't need a priori knowledge of the encryption key. That's literally the whole point. Consider the following (very weak) encryption scheme: m, k ∈ Z[p], E(m) = m * k mod p, D(c) = c * k⁻¹ mod p With this, I can implement a service that receives two cyphertexts and computes their encrypted sum, without knowledge of the key k: E(x) + E(y) = x * k + y * k mod p = (x + y) * k mod p = E…
In the case of searching Google, E(x) is the encrypted query and y is Google's database. Can you compute E(x + y) without doing at least as much work as computing E(y)? I don't think so. Instead, you use public key cryptography so that the server can compute E(y) (yes, encrypting the entire database) without being able to decrypt D(E(x)) = x.
E.g. consider the following system:
E(x) = x ^ k, D(x) = x ^ k
So a one-time pad. Let's say that I provide a service that lets you decide whether a number is even or odd:
IsOdd(E(x)) = E(x) mod 2
You give it an encrypted number, and it gives you back an encrypted bit that you can decrypt to see if the original number was even or not. All while it has zero knowledge of your plaintext number.
A homomorphically encrypted database is just like IsOdd(x), except orders of magnitude more complex. One idea is that any computation can be turned into a Boolean circuit, so if you have homomorphic building blocks for Boolean circuits, you can implement any computation. Obviously, some caveats apply, like all loops have to be unrolled, etc. That's why the whole thing is so inefficient. But mathematically it works.