Where does bootstrapping occur, client side or server side?

Question

In Fully Homomorphic Encryption, where does the bootstrapping procedure performed, in the client-side or the server-side?

Also, which side holds the secret key and the public key?

Answer 1

The aim of Fully Homomorphic Encryption (FHE) is out-sourcing the computation, especially onto the cloud or from a small computing devices into a more capable one securely. FHE was the holy grail of Cryptography that waited for around 30 years to be found, mentioned On data banks and privacy homomorphisms by Rivest.

In FHE schemes we are talking about circuit computation that is similar to electronics but this time mathematically. For semantical security, a noise is added and this is the main problem when performing FHE operations - i.e. dealing with the noise.

When circuit operations are performed with the used FHE scheme the noise increases. Especially the multiplication is problematic - doubling the noise. After a threshold is passed you can no longer decrypt the ciphertexts. For example in Fully Homomorphic Encryption over the Integers

$$c \leftarrow m + 2r + 2x$$ where $m \in \{0,1\}$, $r$ is the random (noise), and $x$ is the public key (note: here $x$ part it is simplified)

The bootstrapping is the novel idea given to us by Gentry. Before reaching the threshold, Gentry showed that we can run the circuit of the decryption algorithm of his scheme, and provide ciphertexts to this decryption circuit and encryption of the private key. In the end, we will get new ciphertext but the noise is reduced.

Now, if we turn into your question. For an FHE circuit, actually, you calculate the depth requirement and possible techniques available on your selected scheme, like bootstrapping, re-linearization, and modulus switching. Once you designed and implemented your circuit, you send all the information to your outsource to compute (in FHE terms $\texttt{EVAL}$). If you need bootstrapping at some point to reduce the noise, you already provide the necessary information on your circuit and designed it with bootstrapping. Yes, actually, bootstrapping is a part of your circuit. There is no need for interaction. Fire and forget until the result is returned to you.

For the comment :

You prepare your circuit $\mathcal{C}$ and supply the required parameters for the evaluation; $$\texttt{EVAL} (k_{pub}, \mathcal{C}, c_1,\ldots,c_l, E_{k_{pub}}(prv))$$ where the $c_1,\ldots,c_l$ are the encryption of the plaintext, i.e. $c_i = E_{k_{prv}}(p_i)$, $k_{pub}$ is your public key, and encryption of your private key $E_{k_{pub}}(prv))$ if bootstrapping is required.

As always;

• you keep the private key secret to yourself, and
• the public key is public.