Fully Homomorphic Encryption II
summary
Shows how bootstrapping/recryption turns a bounded-depth GSW-style scheme into fully homomorphic encryption by homomorphically evaluating decryption, with the public key including encrypted secret bits and relying on circular security. Uses modulus reduction (scales down Q to P) plus short-secret LWE to make the decryption circuit shallow and get polynomial LWE hardness. Builds a CRS-based multi-key construction by encrypting randomness and assembling correction matrices; noise and key size grow only linearly, and the method works.
AI-written summary · about
chapters (17)
- 0:00Intro
- 0:43Fully Homomorphic Encryption (FHE)
- 1:53A Digression into Philosophy...
- 3:01Philosophy Meets Cryptography
- 5:12Recryption: Refreshing a Ciphertext
- 7:33Bootstrapping Theorem (Informal)
- 8:37Recryption for GSW
- 13:44How Complex Is Decryption?
- 19:13Modulus Reduction Magic Trick, Notes
- 21:51Evaluating NC1 Circuits in GSW
- 29:21Multi-Key Homomorphic Encryption
- 34:58A Variation of GSW
- 42:28Fixing the Algebraic Trick
- 45:14Summary So Far: Algebraic Trick
- 45:59Related Public Keys
- 49:07Step 3: "Masking Scheme" for GSW
- 59:08What We Covered Today
related talks
01h 07mLattices and Encrypted Computation
54mFully Homomorphic Encryption
23mBootstrapping Homomorphic Encryption via Functional Encryption
01h 01mMulti-key FHE and Spooky Encryption
46mRunning Circuits of Unbounded Depth over Encrypted Data, Securely, Using Lattices...
37mCircularity Based IO, Part 2
01h 01mCircularity Based IO, Part 1
41mHomomorphic Commitments & Signatures