Gate Bootstrapping

In Fully Homomorphic Encryption #FHE, one can perform computation over encrypted data (messages) without first decrypting the messages. However during computations the noise (du to the LWE) grows quickly and can reach a stage where decryption will not be possible. Then we need a tool in order to retrieve the messages we've encrypted. That tool is called the #Bootstrapping.

According to C.Gentry the Gate Bootstrapping is a procedure which allows to reduce the noise on encrypted data during the different evaluation. Sometime we talk about #PBS (by zama).

To Handle the Bootstrapping we need 4 different steps to follow :

• First : we need to do the #Module_Switching to pass from a module q to 2N
• Second : the #Blind_Rotation in order to rotate data from a current position an other one.
• Third : the #Sample_Extraction to extract coefficients of the polynomial got from the #Blind_Rotation.
• Fourth : the #Key_Switching as its name can indicate we switch from the current set of parameters (#RLWE) to the initial parameters (#LWE).

During the #Bootstrapping procedure the noise is decreased at the end of the procedure, nevertheless the noise is a little bit increase during #Module_Switching to #Blindo_Rotation.

In the #Blind_Rotation we use a polynomial called #Test_Polynomial so as to test all unknown position in the polynomial we want to test in order to retrieve the data we want to get access without decrypting them.

A cyclic group can be taken to build the schemes but a cyclic group is not safe enough against certain attacks, and to perform the #Blind_Rotation.

I hope that this post will be useful for those who currently are working on #FHEs.