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$
Full adder
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.
n-bit Full adder
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;
