Fully Homomorphic Encryption I
summary
Explains a concrete LWE-based GSW scheme that turns ciphertexts into matrices and uses a gadget matrix/G inverse decomposition so long-entry matrices become larger matrices with small entries. Claims semantic security from LWE, additive homomorphism by matrix addition, and multiplication by expanding one operand then multiplying; the noise multiplies by ~M per multiplication, limiting multiplications to about log_{M+1} Q depth. Demonstrates a workable somewhat-homomorphic construction and the path to bootstrapping for full FHE.
AI-written summary · about
chapters (29)
- 0:00Intro
- 0:24Computing on Encrypted Data
- 2:34Homomorphic Encryption (HE)
- 4:04An Analogy: Alice's Jewelry Store
- 5:51HE Security: A Paradox?
- 7:27Some Properties
- 9:46Secret-key vs. Public-key HE
- 11:26Transforming HE from SK to PK
- 13:29FHE Doesn't Do Obfuscation
- 14:29FHE Doesn't Do RAM
- 15:52FHE Doesn't Do Multi-Key
- 16:57A Toy HE Scheme (from American Scientist magazine)
- 17:53About "Homomorphism"
- 20:23Noisy Ciphertexts
- 21:02Example: SWHE over the Integers
- 23:43The Noise Problem Hurts Efficiency. Why?
- 25:39Regev's Encryption Scheme
- 27:56Properties of Regev's Scheme
- 29:06Homomorphic ADD in Regev
- 29:40Homomorphic MULT in Regev
- 30:58Matrix Version (1 stry)
- 33:24Homomorphism in Error-Free Setting
- 34:11Homomorphism with Error (1st try)
- 35:35Controlling the Noise
- 37:42Gadget for Flattening
- 38:34Example of a Gadget Matrix
- 39:39Modified Matrix Encryption
- 41:08Homomorphic Multiplication
- 42:35Summary of GSW
related talks
54mFully Homomorphic Encryption
01h 07mLattices and Encrypted Computation
57mTutorial: Encrypted Computation from Lattices
01h 01mMulti-key FHE and Spooky Encryption
52mSomewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN
01h 07mHomomorphic Signatures and Pre-Processing NIZK
31mIdentity-Based Encryption
44mObfuscation III