# FHE Meeting #5: Gentry 2009 **URL:** \ **Category:** FHE kindergarten\ **Created:** [December 13, 2023, 2:57pm UTC](https://forum.anoma.net/t/fhe-meeting-5-gentry-2009/417 "2023-12-13T14:57:34Z")\ **Posts on this page:** 7\ **Page:** 1
**Author:** ![vveiln](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.anoma.net/vveiln/32/60_2.png) [@vveiln](https://forum.anoma.net/u/vveiln)\ **Post date:** [December 13, 2023, 2:57pm UTC](https://forum.anoma.net/t/fhe-meeting-5-gentry-2009/417/1 "2023-12-13T14:57:34Z")
**Date:** 21.12.23 **Time:** 4pm CET **Reading materials:** - [Fully Homomorphic Encryption Using Ideal Lattices (Section 1)](https://www.cs.cmu.edu/~odonnell/hits09/gentry-homomorphic-encryption.pdf) 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). * * * 1. afaik ---
**Author:** ![graphomath](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.anoma.net/graphomath/32/9_2.png) [@graphomath](https://forum.anoma.net/u/graphomath)\ **Post date:** [December 21, 2023, 10:21am UTC](https://forum.anoma.net/t/fhe-meeting-5-gentry-2009/417/2 "2023-12-21T10:21:56Z")
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 ?) - [Semantic security - Wikipedia](https://en.wikipedia.org/wiki/Semantic_security) - [NC (complexity) - Wikipedia](https://en.wikipedia.org/wiki/NC_(complexity)#The_NC_hierarchy) ---
**Author:** ![graphomath](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.anoma.net/graphomath/32/9_2.png) [@graphomath](https://forum.anoma.net/u/graphomath)\ **Post date:** [December 21, 2023, 10:26am UTC](https://forum.anoma.net/t/fhe-meeting-5-gentry-2009/417/3 "2023-12-21T10:26:12Z")
tangential question > are gates in circuits always commutative operations? context: the typical definitions of circuits (as e.g., in [complexity theory](https://en.wikipedia.org/wiki/Circuit_complexity)) 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 … ---
**Author:** ![graphomath](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.anoma.net/graphomath/32/9_2.png) [@graphomath](https://forum.anoma.net/u/graphomath)\ **Post date:** [December 21, 2023, 1:13pm UTC](https://forum.anoma.net/t/fhe-meeting-5-gentry-2009/417/4 "2023-12-21T13:13:51Z")
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_. * * * 1. \mathsf{Recrypt} implies a one-way proxy re-encryption scheme[[10]](https://link.springer.com/chapter/10.1007/BFb0054122). ---
**Author:** ![0xnagu](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.anoma.net/0xnagu/32/279_2.png) [@0xnagu](https://forum.anoma.net/u/0xnagu)\ **Post date:** [January 3, 2024, 3:19pm UTC](https://forum.anoma.net/t/fhe-meeting-5-gentry-2009/417/5 "2024-01-03T15:19:59Z")
This github repo has some great list of papers on FHE. > **[GitHub - BUAA-CI-Lab/Literatures-on-Homomorphic-Encryption: A reading list...](https://github.com/BUAA-CI-Lab/Literatures-on-Homomorphic-Encryption)** > > A reading list for homomorphic encryption. Contribute to BUAA-CI-Lab/Literatures-on-Homomorphic-Encryption development by creating an account on GitHub. ---
**Author:** ![0xnagu](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.anoma.net/0xnagu/32/279_2.png) [@0xnagu](https://forum.anoma.net/u/0xnagu)\ **Post date:** [January 6, 2024, 2:30pm UTC](https://forum.anoma.net/t/fhe-meeting-5-gentry-2009/417/6 "2024-01-06T14:30:38Z")
@vveiln Are we meeting next week? Are we continuing with the Gentry paper? ---
**Author:** ![vveiln](https://dub1.discourse-cdn.com/flex013/user_avatar/forum.anoma.net/vveiln/32/60_2.png) [@vveiln](https://forum.anoma.net/u/vveiln)\ **Post date:** [January 7, 2024, 8:50am UTC](https://forum.anoma.net/t/fhe-meeting-5-gentry-2009/417/7 "2024-01-07T08:50:15Z")
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 πŸ™‚