Fully Homomorphic Boolean Gates

Other, random and misc
1

Dear community,
In the publication of I. Chillotti, N. Gama, M. Georgieva and M. Izabachene, “TFHE: fast fully homomorphic encryption over the torus” I found these gate descriptions that I would love to understand. I hope for your help in answering a few questions I have about them or mentioning materials that would help me.

– HomNOT(c) = (0, 1/4) - c
– HomAND(c1, c2) = Bootstrap ((0, -1/8) + c1 + c2)
– HomNAND(c1, c2) = Bootstrap ((0, 5/8) - c1 - c2)
– HomOR(c1, c2) = Bootstrap ((0, 1/8) + c1 + c2)
– HomXOR(c1, c2) = Bootstrap (2 · (c1 - c2 ))

I noticed that in the TFHE Library (TFHE Fast Fully Homomorphic Encryption over the Torus) the NAND and XOR gates are different:
– HomNAND(c1, c2) = Bootstrap ((0, 1/8) - c1 - c2)
– HomXOR(c1, c2) = Bootstrap ((0, 1/4) + 2*(c1 + c2))
also, the NOT gate seems to be just:
– HomNOT(c) = - c

  1. How do we derive that for example, NAND is (- c1 - c2) or OR is (+ c1 + c2)
  2. Where are the constants like -1/8 or 1/4 coming from?
  3. What is the reason for the differences between the gates in the publication and the library?

I understand that these are very specific questions, but maybe you can give me some clues.
Thank you!

2

Dear @MichaelP,

Thanks for your question and for your interest in TFHE :slight_smile:

The original gates supposed that the encoding for the bit 0 was 0 and the encoding for bit 1 was 1/4 (or q/4). The reason of using these values instead of 0 and 1/2 is to keep a bit empty to be able to perform the initial linear combination. After the linear combinations inside the parenthesis of bootstrapping, the bootstrapping would perform an evaluation of the “sign function”.

The encoding in the TFHE library is in practice the same, just shifted the original encoding of -1/8 (or -q/8), to make everything “symmetric”. So the bit 0 is encoded as -1/8 (or -q/8) and the bit 1 is encoded as 1/8 (or q/8). The linear combinations are then adapted to the new encoding, and, as instance, the not gate can be easily expressed as a negation.

For a detailed explanation of the technique, I suggest you to take a look to the section " An example of bootstrapping: the Gate Bootstrapping" in the blogpost TFHE Deep Dive - Part IV - Programmable Bootstrapping . It is short and it takes as an example the AND gate (for the other binary gates the explanation would be the same, just with a different linear combination).

Hope this helps you on your questions. :slight_smile:

Ilaria

1 Like