# Can Fully Homomorphic Encryption do comparisons?

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"?

• FHE can not make you happy or forever young, so why "holy grail" indeed? A reference? Commented Mar 22, 2018 at 8:37
• Here it is : crypto.stanford.edu/~dwu4/papers/XRDSFHE.pdf The power of a fully homomorphic encryption scheme (FHE) lies in the fact that it enables arbitrary computation on encrypted data Commented Mar 22, 2018 at 8:40
• Try read this paper (Comparison-based applications for fully homomorphic encrypted data )[acad.ro/sectii2002/proceedings/doc2015-3s/08-Togan.pdf[. Also, I found this tutorial about HE youtube.com/watch?v=jIWOR2bGC7c very useful. Commented Mar 24, 2018 at 16:12

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).

• 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. Commented Mar 22, 2018 at 8:18
• @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. Commented Mar 22, 2018 at 8:23
• Edited the post. Commented Mar 22, 2018 at 8:27
• @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).
– j.p.
Commented Mar 22, 2018 at 8:29
• No, no need for such assumptions. There are boolean circuits that take as input the bits of $a$ and $b$, and output a bit equal to 1 iff $a > b$, performing only XORs and ANDs (i.e., additions and multiplications over $\mathbb{F}_2$). See e.g. this paper, page 7. You can just homomorphically evaluate any such boolean circuit on bit-by-bit encryptions of your data with FHE. Commented Sep 12, 2019 at 14:09

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.

• 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) Commented Mar 22, 2018 at 8:46
• @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. Commented Mar 22, 2018 at 8:51
• 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". Commented Mar 22, 2018 at 8:52
• @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? Commented Mar 22, 2018 at 9:18
• 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. Commented Mar 22, 2018 at 9:26