3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Maybe I don't understand what you're asking. E(M) is encrypted. The cloud service doesn't know the key. So whatever it does to E(M) without the key, all it can produce is encrypted results that it cannot make sense of. The only correspondence between M and anything in E(M) comes from the encryption scheme. $\endgroup$ – David Schwartz Feb 17 '17 at 22:30
  • 1
    $\begingroup$ If sounds like you expect/think FHE is a deterministic encryption. FHE is not, and can not securely be, deterministic. The probability of two identical plaintext values being represented by the same ciphertext is diminishingly small. This is not an uncommon misunderstanding, I've seen it before. $\endgroup$ – Thomas M. DuBuisson Feb 19 '17 at 19:00
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – e-sushi Feb 19 '17 at 13:20
  • $\begingroup$ Thanks for editing, much better answer now that it's clear you're only giving a high level overview of why it should "feel" safe in some specific use case, instead of any kind of general or rigorous argument. I had assumed that people can use Wikipedia themself, so it's good that you see they need the obvious stated, and aren't ready for any level of rigor yet. $\endgroup$ – MickLH Feb 20 '17 at 17:04
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ you mean $F(E(m))$? $\endgroup$ – 111 Feb 19 '17 at 0:19
  • 2
    $\begingroup$ No. That's the mistake of the asker that I've corrected. It is actually $F'(E(m)) = E(F(m))$, the actual function applied to the ciphertext may be strange. It is the effective function that we care about. $\endgroup$ – MickLH Feb 19 '17 at 4:10
  • 1
    $\begingroup$ Not sure, what do you mean. But a FHE scheme has an evaluator, ${\it Eval}$ which is an efficient algorithm and a function (usually implemented as a circuit) say F, such that if $c=Enc(m)$ then $Dec(Eval(F,c))=F(m).$ So with $E(F(m))$ perhaps you mean ${\it Eval}(F,c)?$ Cloud can not work directly with the plaintext $m.$ $\endgroup$ – 111 Feb 19 '17 at 19:14
  • 1
    $\begingroup$ $F'(x) = \text{Eval}(F, x)$ Everything you've said is extremely obvious and you clearly have not taken the time to understand why I've given a more detailed answer than your extremely obvious rambling there. You're wasting my time and I'm feeling quite silly for sketching a rigorous argument when clearly the community isn't even at Wikipedia level on the topic yet. :( $\endgroup$ – MickLH Feb 20 '17 at 17:06
  • $\begingroup$ I don't think that is obvious. The notation you used is not very sound since the cloud can not compute $E(F(m)),$ unless you clearly state what you mean. Also, if you feel that you are wasting your time, you have the option not to answer to the comments! $\endgroup$ – 111 Feb 20 '17 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.