Fully homomorphic encryption arbitrary functions formulation
Suppose we want to compare two integers X and Y binary represented as X=x_0,x_1,...,x_n and Y=y_0,y_1,...,y_n. Comparing X and  Y translates to bit comparison, from the msb to lsb; therefore a toy example is to consider two bit comparison, x and y. The binary expressions(computation is done in Z_2) corresponding to three of their possible relations are the following:

x &gt; y &lt;=&gt; x*y + 1 = 1
x = y &lt;=&gt; x + y + 1 = 1
x &lt;= y &lt;=&gt; x*y + x + 1 = 1


This means that if we have the FH encryptions of x and y, namely C_x and C_y, we can evaluate C = C_x*C_y+C_x . Upon decryption of C, one can know if x>y (i.e. Dec(C)=1) or x&lt;=y (i.e. Dec(C)=0).

Then you simply extend the above solution for n bits, namely you express conditions like ANDs as multiplications and conditions like ORs as additions.

For two bit integers, X=x_0,x_1 and Y=y_0,y_1, for comparison X > Y to be true, we have the following possibilities:
    x_0 > y_0 or
    x_0 = y_0 and x_1 > y_1.

Using comparison functions defined above for a single bit we have ( keep in mind that we treat OR as addition and AND as multiplication):

greaterThan(x,y) = ( x_0 &gt; y_0) OR ( (x_0 = y_0) AND (x_1 &gt; y_1) )
             = ( x_0*y_0 + x_0) + [ (x_0*y_0 + x_0 + 1) * (x_1*y_1 + 1)]


And that's all, you have a function ( greater than) expressed as a multivariate polynomial which you can write in terms of simple operations ( additions and multiplications). Now the best part is that for these simple operations we know they are homomorphic (namely DEC( ENC(x) + ENC(y) ) = x+y and likewise for multiplication) with respect to some underlying homomorphic encryption scheme (like BGV https://eprint.iacr.org/2011/277.pdf or ATV-FHE https://eprint.iacr.org/2013/094.pdf).

*-denotes bitwise multiplication

Please improve this answer by editing the mathematical notations.