2
$\begingroup$

In Fully Homomorphic Encryption scheme represented here Fully Homomorphic Encryption over the Integers

In the Evaluate process (see section “3.1 The Construction” of the paper): $$Evaluate(pk, C, c1, \dots , ct):$$

Now…

  1. If I want to do some operations on an encrypted data, should I convert that operation to a binary circuit, then do the operation, and re-encrypt the final result?

  2. If I have this simple binary circuit below, how could I evaluate the process?

    Simple binary circuit to compute

  3. What is the data that will be passed to the Input A and input B?

  4. And how can I determine the number of addition and multiplication operations that will be used?

I did not understand how to do it from the Paper.

$\endgroup$
5
$\begingroup$

It's actually straight-forward; we'll assume that all the inputs are either encrypted versions of 0, or encrypted version of 1; then:

  • We can replace an AND gate with just an FHE multiplication of the two inputs:

    $$AND(x,y) = x*y$$

    Where $*$ is our Homeomorpic multiplcation operation. This obviously evaluates to an encrypted 1 if both of the inputs are encryped 1's; and an encrypted 0 if either of the inputs are encryped 0's

  • To replace an exclusive or gate, we encrypt the constants 1 and -1, and then compute:

    $$XOR(x,y) = x*(1 + (-1 * y)) + y*(1 + (-1 * x))$$

    Where + is our homeomorphic addition operation, and 1 and -1 stand for our encrypted constants.

  • To replace an or gate, we take our encrypted 1 and -1 constants, and compute:

    $$OR(x,y) = 1 + -1 * (-1 + x) * (-1 + y)$$

  • To replace a NOT gate (that doesn't appear in your circuit, but does come up in others), we compute:

    $$NOT(x) = 1 + -1 * x$$

It is easy to see that, in all cases, if the inputs are restricted to encrypted 0 and encrypted 1, the result is either an encrypted 0 or an encrypted 1 (and which will be the logical result of the operation). Obviously, things can be simplified somewhat if our FHE operation includes a subtraction operation.

As for the number of operations used, we just translate each gate and count them up. On the other hand, this construction is really a proof that just addition and multiplication suffice to be complete operations (that is, given just those two operations, we can compute anything); when you look at operation count, it turns out to be quite inefficient.

$\endgroup$
  • $\begingroup$ The fact that addition and multiplication can't turn 0s into a 1 shows that they are not complete operations. (However, addition and multiplication and $-1$ suffice to be complete operations.) $\endgroup$ – user991 Sep 23 '14 at 17:57
  • $\begingroup$ @RickyDemer: with FHE, it is assumed that we can take any value, and generate an encrypted form of it with the public key. I assumed that as part of my demonstration; if those aren't available, the problem could include a fixed encryption of -1. $\endgroup$ – poncho Sep 23 '14 at 18:08
  • 2
    $\begingroup$ $XOR(x,y)$ and $OR(x,y)$ can be simplified to $\:x+y+((-2)*x*y)$ $\hspace{2.15 in}$ and $\:x+y+((-1)*x*y)\:$ respectively. $\;\;\;$ $\endgroup$ – user991 Sep 23 '14 at 18:28
  • $\begingroup$ @RickyDemer: cool! $\endgroup$ – poncho Sep 23 '14 at 18:32

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.