Fully-homomorphic encryption

Before ThisWhere Lecture 11 Left Off

Lecture 11 converted lattice trapdoors into deployed standards: Falcon's direct Short Integer Solution (SIS) signature pattern, Crystals-Dilithium's Fiat-Shamir identification pattern repaired by repetition, smallness checks and rejection sampling, Regev encryption with correctness from one cancellation and security from two hybrids, and the Fujisaki-Okamoto transform lifting that Chosen-Plaintext Attack (CPA) scheme to a Chosen-Ciphertext Attack (CCA) secure key encapsulation mechanism standardized as Crystals-Kyber. After this lecture, confidentiality and authenticity both have post-quantum replacements. What remains missing is computation: a server holding ciphertexts cannot evaluate functions on the plaintexts.

This LectureWhat It Adds

This lecture adds fully-homomorphic encryption, the ability to evaluate arbitrary circuits on ciphertexts. It defines the four algorithms and the two requirements, correctness after evaluation and privacy of evaluated ciphertexts, and resolves the apparent branching paradox by requiring randomized encryption. GSW (Gentry-Sahai-Waters) is the concrete scheme: a ciphertext is a matrix for which the secret key is an approximate eigenvector, with the gadget matrix carrying the plaintext and the noise term hiding it. Addition adds matrices and noise; multiplication uses gadget decomposition so the noise grows by the gadget factor per level instead of squaring. The resulting budget gives levelled FHE when the modulus is sized to a depth bound, and bootstrapping removes the bound by homomorphically evaluating the scheme's own decryption circuit, refreshing the ciphertext under the circular security assumption. The stage animates the invariant and the bootstrap refresh. The lab tracks the noise budget through additions, multiplications and bootstraps.

Study PlanWhat to Read, in Lecture Order

1. Chapter 4 §11: Fully-homomorphic encryption. Definition, the trivial construction and why it fails, the GSW (Gentry-Sahai-Waters) invariant, homomorphic addition and multiplication, the depth bound, bootstrapping and circular security. Step through the stage, then use the noise-budget lab to cross the $q/4$ line. Section 12, Identity-Based Encryption (IBE) and Attribute-Based Encryption (ABE) from lattices, belongs to Lecture 13.

PracticeExercises for This Lecture

• An Fully-Homomorphic Encryption (FHE) noise budget: compute the largest multiplicative depth from the GSW (Gentry-Sahai-Waters) correctness bound, then reproduce the cliff in the section 11 lab.