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).

a growing list of pointers to preliminary concepts

circuits are sth. like a special form of node labeled directed acyclic graphs, probably term graphs; the size is the number of inner nodes, i.e., the number of gates (right, @yulia ?)

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.

\mathsf{Recrypt} implies a one-way proxy re-encryption scheme [10]. ↩︎

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