# Representing a function as FHE circuit

I am actually trying to study homomorphic encryption (on lattices) but I'm facing a problem. Every paper that I have read so far talk about writing the function to evaluate on ciphertexts as a circuit, either boolean or arithmetic according to our scheme if I understood this part well. My problem is that I couldn't find explicit documentation on how to turn a function to a circuit.

Especially, in circuits, we can't have loops or conditions and I would have liked to apply my FHE scheme to the weights of a neural network, but I'm kinda stuck on how to represent the activation function (I think I would use the sigmoid, that can be represented with its Taylor expansion) and simple gradient descent.

Does anyone have a clue or a good paper to help me understand how to write such functions to circuits?

• You might want to look at this paper for homomorphic evaluation of neural networks: eprint.iacr.org/2017/1114 Nov 9, 2018 at 12:23

The circuit term in the evaluation of functions with FHE is a coming from Electronics. In the notion of FHE circuit, we have almost the same problem; build a circuit of a function $$f$$ with available FHE operations so that we can evaluate the $$f$$ with FHE.

Somewhat Fully Homomorphic schemes allow us to operations on ciphertexts. In the bitwise case, for example; you will have two operations on the ciphertext bits;

$$E(p_1) + E(p_2) = E(p_1 +p_2)$$ and $$E(p_1) * E(p_2) = E(p_1 *p_2),$$ where $$p_1$$ and $$p_2$$ are plaintext bits and E is a fully homomorphic scheme as;

To evaluate a function $$f$$ with FHE, we consider it's circuit implementation with the two above operations. It is similar to what we do in Electronics, that is; we can build a circuit for $$f$$ by using the binary operations, AND, OR, NOR, etc. and see universal logic gates and Functional Completeness

In FHE we have two operations and this is enough, up to some point. The name Fully is meaning that it supports two operations.

Unfortunately (or fortunately), The FHE schemes are semantically secure, this means that;

$$a = b \not\Rightarrow E(a) = E(b),$$ and even the equality only hold with negligible probability. As a result of this; currently, it is not practical to build a circuit for every function to evaluate.

## Some FHE circuits

In the below demonstrations, I'll stick to HELib based on Fully Homomorphic Encryption without Bootstrapping. Using different schemes may require different circuit implementation. In HeLib case; we have these binary FHE operations on the ciphertext;

• $$+$$ is $$\oplus$$ and
• $$*$$ is $$\wedge$$ opereation.

## NAND Gate

Although the NAND gate is universal, we can construct it by using the AND and XOR

$$A \text{ nand } B = ( A * B ) + 1$$

Let $$A=E(a),B=E(b),C=E(c)$$ we will calulate the sum $$S$$ and carry $$S'$$ as;

$$S= A \oplus B$$ and $$S'= A \wedge B$$, as the usual circuit.

can be implemented same as ripple carry adder

## if/else

we can build it with a 2:1 multiplexer 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.

• 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.

Actually, This is the base of the FHE PIR implementation. Remember all values are encrypted semantically.

## Equality

Given to 2 $$n$$-bit numbers $$x$$ and $$y$$;

• $$x= \{x_{n-1}, \ldots, x_{0}\}$$
• $$y= \{y_{n-1}, \ldots, y_{0}\}$$

with the FHE encrypted values;

• $$X= \{E(x_{n-1}), \ldots, E(x_{0})\}$$
• $$Y= \{E(y_{n-1}), \ldots, E(y_{0})\},$$

where $$X$$ and $$Y$$ holds the encrypted lists of $$x$$ and $$y$$.

we can compute two plaintext equality under FHE by using the following circuit;

• component wise $$\oplus$$, $$Z = \{E(x_{n-1}) \oplus E(y_{n-1}),\ldots,E(x_{0}) \oplus E(y_{0})\}$$
• component wise invert; $$Z' = Z \oplus \{E(1),\ldots,E(1)\}$$
• $$\wedge$$ the bits; $$R = z'_0 \wedge \ldots \wedge z'_n$$

$$R = \begin{cases} E(1), & \text{if equal} \\ E(0), & \text{else} \end{cases}$$

To reduce the depth of the $$\wedge$$, a binary tree is preferred.

## Comparison

Calculate comparsion by $$\operatorname{C}(X,Y) = \operatorname{MSB}(X-Y)$$ and 2's complements. This will keep $$1$$ if $$X \geq Y$$ and $$0$$ if $$X < Y$$

## Sorting SWAP with FHE

The swap of two FHE variable can be performed by the following equation;

$$\operatorname{SWAP}(X,Y) = X*\overline{\operatorname{C}(X,Y)}+ Y*\operatorname{C}(X,Y), X*\operatorname{C}(X,Y)+ Y*\overline{\operatorname{C}(X,Y)}$$

where the overbar represents the complement.

Note that; the server doesn't know the output and doesn't need to know the real plaintext of the Comparison to perform a swap. This $$\operatorname{SWAP}$$ routine is used in sorting implementations that require a swap function (usual in comparison-based sortings), according to the FHE encrypted comparison $$C$$ result, the values are either swapped or not swapped and the server still doesn't know.

## Some implementations articles;

• Concerning the computation of plaintext equality, I have trouble understanding the process, because, as you pointed it out, FHE schemes are semantically secure. So how can this circuit be efficient as 2 different encryptions of the same bit can differ? Even if I understand (I think) the circuit, I don't see how a probabilistic scheme can be applied here.. Nov 8, 2018 at 23:43
• They are not efficient and maybe never will be. The semantic security force you to construct with different circuits that are valid and produce the same result in Electronics but slower, as in addition. Nobody uses ripple carry adder. Nov 9, 2018 at 7:09
• Forgive me if I wasn't precise enough, when I was wondering about the efficiency, I meant the validity of the circuit. (as we can't be sure that R will be equal to E(0) or E(1) due to the probabilistic encryption scheme? Nov 9, 2018 at 7:32
• We are sure about the value but the server doesn't know. For example, if asked the server to sort a list by the Bubble Sort algorithm. It needs to compare and according to the result, it will swap. A swap in the electronics circuit is just wiring bu the swap in FHE is as in the answer. Look it carefully. Nov 9, 2018 at 7:47
• @DanielK there complement. Feb 17, 2020 at 15:42