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?

New contributor
Robin S. is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
  • IF you are talking about Especially circuit as a classical combination of logical operations in electronics, a simple if/ else is 2:1 multiplexer – kelalaka Nov 8 at 9:37
  • You might want to look at this paper for homomorphic evaluation of neural networks: eprint.iacr.org/2017/1114 – pscholl Nov 9 at 12:23
up vote 4 down vote accepted

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.

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 $C(X,Y) = MSB(X-Y)$ and 2's complements.

Sorting SWAP with FHE

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

$$ SWAP(X,Y) = X*C(X,Y)+ Y*C(X,Y)', X*C(X,Y)'+ Y*C(X,Y)$$

Note that; the server doesn't know the output and doesn not need to know the real plaintext of the Comparison to perform a swap. This $SWAP$ routine is used in sorting implementations for the swap function, 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.. – Robin S. Nov 8 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. – kelalaka Nov 9 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? – Robin S. Nov 9 at 7:32
  • 1
    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. – kelalaka Nov 9 at 7:47

Your Answer

Robin S. is a new contributor. Be nice, and check out our Code of Conduct.
 
discard

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.