Date: 21.12.23
Time: 4pm CET
Reading materials:
Hey everyone, we are back! 
The last FHE meeting of this year will be about the first real[1] FHE paper, written by Craig Gentry in 2009. The encryption scheme is based on lattices, but don’t worry if you are unfamiliar with them - we will only cover the introduction this time (and you can ignore everything about lattices while reading).
afaik ↩︎
a growing list of pointers to preliminary concepts
tangential question
are gates in circuits always commutative operations?
context: the typical definitions of circuits (as e.g., in complexity theory) do not specify the order of the arguments that are fed into a gate
one could accomodate for this by using directed (ordered) hypergraphs, but well, I guess, the core of the FHE problems are elsewhere …
I think, the following part is what I am most excited about (especially how to understand the first occurrence of bootstrappable and the last one, and the full story of augmentation).
This is the idea behind bootstrapping: we do decrypt the ciphertext, but homomorphically!
Specifically, suppose \mathcal{E} is bootstrappable with plaintext space \mathcal{P} is \{0, 1\}, and that circuits are boolean. Suppose we have a ciphertext \psi_1 that encrypts \pi under \mathrm{pk}_1, which we want to refresh. So that we can decrypt it homomorphically, suppose we also have \mathrm{sk}_1, the secret key for \mathrm{pk}_1, encrypted under a [
] second [
] public key \mathrm{pk}_2: let \overline{\mathrm{sk}_{1j}} [(j=1,\dotsc,|\mathrm{sk}_1|)] be the encrypted secret key bits. Consider the following algorithm.
\mathsf{Recrypt}_{\mathcal{E}} (\mathrm{pk}_2 , D_{\mathcal E} , \langle\overline{\mathrm{sk}_{1j}}\rangle , \psi_1 ).
~~~~~~~\mathrm{Set}~ \overline{\psi_{1j}} \stackrel{\mathrm R}{\gets} \mathsf{Encrypt}_{\mathcal E} (\mathrm{pk}_2 , \psi_{1j} ) \color{lightgray}[j=1,\dotsc,|\psi_1|)]
~~~~~~~\mathrm{Output}~ \psi_2 ← \mathsf{Evaluate}_{\mathcal E} \Bigl(\mathrm{pk}_2 , D_{\mathcal E} , \bigl\langle\langle \overline{\mathrm{sk}_{1j}} \rangle, \langle \overline{\psi_{1j}} \rangle\bigr\rangle\Bigr)
Above, \mathsf{Evaluate}_{\mathcal E} takes in the bits of \mathrm{sk}_1 and \psi_1, each encrypted under \mathrm{pk}_2. Then, \mathcal E is used to evaluate the decryption circuit D_{\mathcal{E}} homomorphically. The output \psi_2 is thus an encryption under \mathrm{pk}_2 of \mathsf{Decrypt}_{\mathcal E} (\mathrm{sk}_1, \psi_1) = \pi.[1] Applying the decryption circuit D_{\mathcal E} removes the error vector associated to the first ciphertext, but \mathsf{Evaluate}_{\mathcal{E}} simultaneously introduces a []new error vector[]. Intuitively, we have made progress as long as the second error vector is shorter.
Suppose C_\mathcal{E} contains not just D_{\mathcal E} but also the augmentation of D_{\mathcal E} by NAND (i.e., a NAND gate connecting two copies of D_{\mathcal E}). Then, we say \mathcal E is bootstrappable.
This github repo has some great list of papers on FHE.
@vveiln Are we meeting next week? Are we continuing with the Gentry paper?
Each meeting is announced as soon as possible, latest by Monday the week of the meeting. If I don’t announce it by Monday, I cancel it for the week. The announcement will contain all the necessary information to prepare 