1
$\begingroup$

I encountered a simple function that even FHE cannot solve. Here's it:

int f(a,b,c,d){
   if(a+b>c+d) return a+c;
      else return b+d;
}

Since FHE is not order-preserving, one can't figure out whether a+b>c+d without the decryption key. That means even if practical FHE was implemented, f(a,b,c,d) cannot be computed in the Cloud independantly and securely. Not to mention linear regression, or more complex functions.

So I wonder with such an obvious limitation, why is FHE called "the holy grail of cryptography"?

$\endgroup$
9
$\begingroup$

This is simply not true. The above function can perfectly be homomorphically computed on FHE ciphertexts encrypting the inputs. There is no such "obvious limitation", and I wonder where your certainty comes from.

Asking whether FHE is Turing complete does not really make sense: FHE is a cryptographic primitive, not a general computing device. If this is what you meant, yes, we can evaluate any (polysize) function on encrypted inputs using the FHE evaluation algorithm. More precisely, we can evaluate any polysize boolean circuit on the input, in a private way (i.e. the inputs and the outputs are not leaked). If you want to evaluate Turing machines, it is more complicated in general (and you must give up on hiding the exact running time of the computation for this to be interesting), but it can also be done.

EDIT: from your comments, I now understand your question more clearly. Yes, FHE will never reveal the intermediate computation in the clear. This means that when you run a program on encrypted values, the computation pattern will have to be oblivious of the exact data. This does not make such computation impossible, as you seem to believe, but simply less efficient.

For example, suppose that you must evaluate the following program: if $a > b$, output $f(x)$, otherwise, output $g(x)$. Using FHE, you would proceed as follows: compute the bit $\beta$ which is $1$ if $a > b$, and $0$ otherwise, and output $\beta\cdot f(x) + (1-\beta)\cdot g(x)$. You can compute this on encrypted data, and you never need to know the exact value of $\beta$ to evaluate this program with FHE.

The FHE computation does not need "the plaintext result", it simply must rely on an algorithm which works obliviously of the exact inputs, and it is usually not hard to convert a computation in an oblivious computation (although it's not always obvious either).

$\endgroup$
  • $\begingroup$ Is it? I've asked help from several crypto experts and failed. Revealing the boolean value of (a+b>c+d) requires the secret key. Which means the data owner has to be heavily involved. $\endgroup$ – vince.h.c Mar 22 '18 at 8:18
  • 2
    $\begingroup$ @vince.h.c There seems to be a very fundamental misunderstanding what FHE is. Evaluating a function in FHE reveals absolutely nothing about the input. $\endgroup$ – Maeher Mar 22 '18 at 8:23
  • $\begingroup$ Edited the post. $\endgroup$ – vince.h.c Mar 22 '18 at 8:27
  • $\begingroup$ @vince.h.c Adding to what Maeher already (correctly) commented, evaluating a function in FHE reveals absolutely nothing about the output either (as the output is encrypted). $\endgroup$ – j.p. Mar 22 '18 at 8:29
  • $\begingroup$ @j.p. Yep, but I mean, most functions in real life require the plaintext result of the output to run the work flow , like if (a > 5), if (a>b) , and FHE cannot do such functions. $\endgroup$ – vince.h.c Mar 22 '18 at 8:32
5
$\begingroup$

The problem seems to be a fundamental misunderstanding about the functionality actually offered by a fully homomorphic encryption scheme.

The functionality of an FHE scheme is that given ciphertexts $c_1\gets \mathsf{Enc}(pk,a)$, $c_2\gets \mathsf{Enc}(pk,b)$, $c_3\gets \mathsf{Enc}(pk,c)$ and $c_4\gets \mathsf{Enc}(pk,d)$ and a function $f$ described as a boolean circuit there exists an algorithm $\mathsf{Eval}$ such that the ciphertext that results from $$c' \gets \mathsf{Eval}(pk,f,c_1,c_2,c_3,c_4)$$ will decrypt to $\mathsf{Dec}(sk,c') = f(a,b,c,d)$.

Note that this does not reveal any information about $a,b,c,d$ or $f(a,b,c,d)$ unless you are in possession of the secret key $sk$.

Therefore you can indeed homomorphically evaluate the function

int f(a,b,c,d){
   if(a+b>c+d) return a+c;
   else return b+d;
}

as it can be represented by a (relatively large) boolean circuit and you will not be able to tell which branch in the program was taken unlss you know the secret key.

$\endgroup$
  • $\begingroup$ Thank you, does it mean that the circuit contains all the possible branches? That will be infeasible for most functions (Guess we are doing linear regression on an encrypted data set) $\endgroup$ – vince.h.c Mar 22 '18 at 8:46
  • $\begingroup$ @vince.h.c I'm not sure that I understand your question. Any polynomial time Turing Machine has an equivalent uniform polynomial size circuit family. So any efficient computation can be represented by a polynomial size circuit. $\endgroup$ – Maeher Mar 22 '18 at 8:51
  • 1
    $\begingroup$ Linear regression on data encrypted with FHE was done several times, see e.g. this article that I picked at random. A polytime computation, even with many branches, can be represented by a polysize boolean circuit, hence be evaluated "efficiently". $\endgroup$ – Geoffroy Couteau Mar 22 '18 at 8:52
  • $\begingroup$ @GeoffroyCouteau Got it. Then it must be a heavy job to design a compiler to translate normal functions(with if-else, comparison, loops) into boolean circuits. Are there any compilers now? $\endgroup$ – vince.h.c Mar 22 '18 at 9:18
  • 3
    $\begingroup$ Yes, and it is even an active research area - compiling any computation into a boolean circuit is straightforward, but optimizing it, making it truly efficient, is way harder. See e.g. Secure Two-party Computations in ANSI C - but dozen of other references exist, which attempt to automatically translate a program described with a high-level language into a boolean circuit optimized for secure computation. $\endgroup$ – Geoffroy Couteau Mar 22 '18 at 9:26

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.