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?

  • $\begingroup$ but which side holds the secret key and the public key? $\endgroup$ – fallere456 Aug 28 '19 at 11:47

The aim of Fully Homomorphic Encryption (FHE) is out-sourcing the computation, especially onto the cloud or from small computing device 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 providing ciphertexts to this decryption circuit and encryption of the private key. In the end, we will get new ciphertext but the noise is gone.

Now, if we turn in to your question. For an FHE circuit, actually, you calculate the depth requirement and possible techniques available on your selected scheme, like bootstrapping, re-linearization, 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 prapere 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.
| improve this answer | |
  • $\begingroup$ Is there any other term we can use other than "circuit"? $\endgroup$ – fallere456 Sep 2 '19 at 12:10
  • $\begingroup$ @fallere456 I don't now. The circuit is common. $\endgroup$ – kelalaka Sep 9 '19 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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