From what I've read I know that FHE requires "circuits" to construct functions and gates to operate on the FHE encrypted data. I've also read that these circuits are constructed from just addition, multiplication, and mixed multiplication. How does this work? How, only using those operations, can we construct a NAND gate for example?

  • 2
    $\begingroup$ I've added the NAND gate to the answer Representing a function as FHE circuit. Now it should cover most of your questions with some links to some implementation articles. Also, you might look at the TFHE library $\endgroup$
    – kelalaka
    Dec 8 '20 at 21:29
  • 1
    $\begingroup$ Over $\mathbb{Z}_2$, multiplication is equivalent to the AND gate and adding $1$ is equivalent to the NOT gate. Finally, NAND(a, b) = NOT ( AND(a, b) ). $\endgroup$ Dec 9 '20 at 11:23