How does bootstrapping work?

hideonjungle

11/2/22, 7:41 AM

I have read FHE lately. In Fully Homomorphic encryption using ideal lattice[Gen09], I noticed his recrypt algorithms:

We have a ciphertext $\phi_1$ which is encrypted by public key $pk_1$, and can be decrypt by secret key $sk_1$.
we use a public key $pk_2$ to encrypt the bits of $sk_1$, and we get $Encrypt_\epsilon(pk_2,sk_{1,j})\to \overline{sk_{1,j}}$.
we use the same public key $pk_2$ to encrypt the bits of $\phi_1$,and we get $Encrypt_\epsilon(pk_2,\phi_{1,j})\to \overline{\phi_{1,j}}$.

Then he said we can get $\phi_2\leftarrow Evaluate_{\epsilon}(pk_2, Dec_{\epsilon}, <<\overline{sk_{1,j}}>,<\overline{\phi_{1,j}}>>)$, and we can still use $sk_1$ to decrypt $\phi_2$.

My question is that how this evaluate work? We can't just run Decrypt cricuit since Decrypt just recieve one secret key and a ciphertext.

Thank you!

0 + 2

homomorphic-encryption

Hilder Vitor Lima Pereira

11/2/22, 1:03 PM

A circuit that adds two 32-bits integers can be viewed as a circuit that has two inputs or 64 inputs... It is basically the same here. Dec is a circuit that receives one ciphertext with, say, n bits and a secrete key with m bits, so the homomorphic evaluation works with n+m ciphertexts encrypting those n+m bits...

kodlu

11/3/22, 7:01 AM

please edit your question and write explicitly what paper GEN09 refers to so the readers can benefit from reading your question.