How can fully homomorphic encryption ever be secure?

Question

Perhaps I am misunderstanding FHE, but from my knowledge, an FHE system is theoretically capable of arbitrary computation. Since this is theoretical talk, let's forget the practicality of actually implementing that today.

A common use case of FHE is secure cloud computation:

1. Encrypt M, call this E(M)
2. Send E(M) to cloud to compute f(E(M)), where f is some arbitrary computation
3. Cloud sends back result and we decrypt to get f(M)

In principle, the cloud never knew M or f(M) as it only operated on ciphertext.

Now my question is: Since this is a FHE scheme that allows arbitrary computation, the cloud service builds a full-text search function on the ciphertext and starts querying E(M) to check for partial matches or even full equality of M. What part of FHE prevents the cloud service from doing this?

Answer 1

Interpreting the question

Firstly, I should state that I interpreted

"Since this is a FHE scheme that allows arbitrary computation, the cloud service builds a full-text search function on the ciphertext and starts querying E(M) to check for partial matches or even full equality of M"

to mean something equivalent to

"What if the cloud service uses the homomorphic properties of the ciphertexts to evaluate a search algorithm which outputs True if the searched substring is contained in the message, or alternatively outputs the matched substring, or returns any arbitrary information about the message. Why can't they abuse this feature to find the message?"

I mention this up front because there appears to be confusion about what exactly the question is asking. This answer will assume that the unspecified homomorphic encryption scheme fulfills its promise of data confidentiality, which for a fully homomorphic scheme, includes evaluating arbitrary circuits while revealing nothing of the plaintext value without evaluating the decryption circuit. Obviously, this does not extend to constants introduced during the evaluation that are created by the service provider via the public key (which they only know because they created the ciphertext).

Answer

With homomorphic encryption, the data is confidential to everyone but the key holder. Anyone can manipulate ciphertexts and evaluate functions on them, but they cannot decrypt the ciphertexts to obtain the result.

What part of FHE prevents the cloud service from doing this?

So the answer is that nothing prevents the cloud service provider from computing a search on the encrypted data - it may compute the search, but it cannot decrypt and view the result of the search. This is because the output of the circuit that is computed is also a ciphertext. The cloud service provider may compute any circuit it wants (assuming the scheme supports it), but the output will always be a bunch of random noise as far the cloud service provider is concerned.

Answer 2

First off, building a table of every possible value of $E(m)$ (even for just one single fixed $m$!) is just a brute force search because we'll have $2^n$ different ways to encode it. So recovering the message that way is out, and as for recovering the key itself: Indistinguishability under chosen-plaintext attack secures the use case you've presented. If we were able to determine anything useful from the output of homomorphic computations, then we would have a serious chosen-ciphertext attack also, because we could simply generate $a \overset{$}\gets \text{Uniform}$ and $b \gets F(a)$, ask for $E(a), E(b)$ and mount the same recovery attack. To see this, lets go over your suggested use case and clear up some details.

1. Encrypt $m$, call this $E(m)$.
2. Send $E(m)$ to cloud to compute $E(F(m))$, where $F$ is some arbitrary computation.
3. Cloud sends back result and we decrypt to get $F(m)$

Notice that the $F$ evaluation is inside the ciphertext. Never does $m$ or any chosen function of $m$ escape from the $E(\cdots)$ box. We could effectively view all possible functions as a sequence of encrypted messages $\{E(m_0),\, E(m_1),\, \cdots\}$ for which we know the difference between them, but we do not know the original $m_0$ value, so none of them are actually determined. We only have ciphertexts with known difference, which is perfectly safe if the cipher is not broken.