2
$\begingroup$

I am currently studying the interesting field of homomorphic encryption. I read that from a fully homomorphic encryption function that supports both addition and multiplication you can perform any mathematical and comparison operations. Ok, but how can you do this specifically? How do you for example perform comparisons ==, <. >= or exponential operations? How about floating number operations?

$\endgroup$
  • $\begingroup$ For exponentiation, see here. For comparison operations, what is the scenario? $\endgroup$ – mikeazo Nov 28 '15 at 19:36
3
$\begingroup$

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 > y <=> x*y + 1 = 1
x = y <=> x + y + 1 = 1
x <= y <=> 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<=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 > y_0) OR ( (x_0 = y_0) AND (x_1 > 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.

$\endgroup$

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.