Fully Homomorphic Encryption

on YouTube ↗54m

" summary

Defines a leveled fully homomorphic scheme built from the learning with errors assumption that encodes messages as eigenvalues for a secret approximate eigenvector so ciphertexts are matrices whose S times C equals message times S G plus small noise. encryption uses A R + M G with a gadget matrix and G inverse to keep entries small and enable homomorphic NAND via C1 · G^{-1}(C2). noise multiplies roughly by n per level so after depth D it grows like n^D, and bootstrapping is required to get unbounded FHE.

AI-written summary · about

" chapters (10)

1. 0:00Intro
2. 2:08Outsourcing Computation - Privately
3. 3:27Fully Homomorphic Encryption (FHE)
4. 11:11Approximate Eigenvector Method [GSW13]
5. 20:23Learning with Errors (LWE) [RO5]
6. 26:40Encryption Scheme from LWE
7. 36:57Binary Decomposition Break each entry in C into its binary representation
8. 38:58Approx. Eigenvector Encryption
9. 50:10Homomorphic Circuit Evaluation
10. 51:17Conclusion

" related talks

• 45mFully Homomorphic Encryption IShai Halevi · Cryptography Boot Camp 2015
• 23mBootstrapping Homomorphic Encryption via Functional EncryptionNir Bitansky, Tomer Solomon · ITCS 2023
• 01h 04mFully Homomorphic Encryption IIShai Halevi · Cryptography Boot Camp 2015
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 47mHomomorphic EncryptionMarc Joye, Tabitha Ogilvie · RSA Conference 2024
• 52mMachine Learning over Encrypted Data with Fully Homomorphic EncryptionBenoit Chevallier-Mames, Jordan Frery · RSA Conference 2023
• 01h 01mMulti-key FHE and Spooky EncryptionDaniel Wichs · Lattices: New Cryptographic Capabilities 2020
• 57mTutorial: Encrypted Computation from LatticesHoeteck Wee · Lattices: New Cryptographic Capabilities 2020