current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 3 down vote favorite

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?

share|improve this question
    
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. – David Schwartz 3 hours ago
up vote 5 down vote

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.

share|improve this answer
    
even in an idealized scenario, saying effectively that nothing prevents you from doing $2^n$ operations (for a security parameter $n$) is not really useful in most cryptographic contexts – MickLH 55 mins ago
    
@MickLH I do not understand the relevance of your comments. If they were criticizing the content of my answer, then they did not help me to see the problem. Saying that "nothing prevents the cloud service provider from computing a search on the encrypted data" is in line with the definition of homomorphic encryption and encrypted computation. Anyone who has your public key can evaluate any circuit they want, but only the private key holder may view the output. I did not not mention 2^n operations or security parameters in my answer, and I fail to see how time/space limitations are related. – Ella Rose 42 mins ago
    
Sorry let me clarify: He's asking about a "search" (actually 2 different searches ambiguously, it's a hazy question) that can allow him to retrieve $m$ given $E(m)$, so that must involve computing all possible values of $E(m)$ for a given $m$ in order to perform a lookup, or must involve a key recovery attack. The schemes are randomized (for semantic security), so $2^n$ different versions of $E(m)$ exist, and that lookup table is out. So you didn't mention that a ciphertext to plaintext search is out, but lets assume that is obvious enough. The real issue is now that you didn't show... – MickLH 27 mins ago
    
...you didn't show why we can safely conclude that no attacker may exploit the ability to produce ciphertexts with any chosen relationship. Intuitively it seems pretty dangerous actually. But we can show that being able to mount an attack like that violates indistinguishably under chosen ciphertexts. This is the critical detail that is missing, which allows us to concretely characterize the effort required to break the scheme. – MickLH 23 mins ago
up vote 2 down vote

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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