I've been wondering for a long time about programs that could potentially break fully homomorphic encryption schemes:

//Given input vector A
if(A[0] == A[1])
   while(true) ; // or do any time consuming calculation
   return <anything>;

System could execute such programs and using timing methods determine information about encrypted data. It could of course ask more clever questions about the data than equality and possibly decode full encrypted vector.

What is wrong with my thinking here?


It is not possible since the IF condition with semantically secure FHE's can be implemented as

$$Q = (A * S) + (B * S'),$$ this circuit is the combinational logic of the if/else statement and we can construct this with FHE.

  • FHE encrypted $S$ is the input by the if statement ( the boolean expression part).
  • FHE encrypted $A$ is the input by the then statement
  • FHE encrypted $B$ is the input by the else statement
  • FHE encrypted $Q$ is the output of the expression.

This is for calculation of the ternary operator Q = S ? A : B;

The IF condition must be implemented in this way. This is due to the semantical security that prevents the output of the comparison circuit to be known to the evaluator. The above circuit will reveal nothing to any observer. Actually, a similar calculation is also performed during normal programming to mitigate the side-channels.

Note that the == can be achieved with 2's complement and substruction. For a little detail see this answer : Representing a function as FHE circuit

One might also wonder that does the comparison circuits in FHE are constant timing, the answer yes since we don't have IF then return/break statements.


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.