Multi-key FHE and Spooky Encryption

on YouTube ↗01h 01m

" summary

Defines multi-key FHE that converts per-user GSW ciphertexts (all reusing a public matrix B) into a single expanded ciphertext under a concatenated secret so homomorphic ops work across users, and shows distributed decryption as per-user inner products that sum to the plaintext. Key technical gadget: publish GSW encryptions of the encryption randomness so one can homomorphically form the unmasking matrix D; yields two-party spooky FHE (secret-shared outputs) and two-round MPC; general n-party spooky uses a GMW-style compilation.

AI-written summary · about

" chapters (11)

1. 0:00Start
2. 5:52Background on Multi-Key FHE
3. 17:48Physical Analogy
4. 23:24Multi-Party Computation
5. 27:31GSW FHE: Encryption
6. 29:25The GSW FHE: Evaluation
7. 31:40Homomorphic Circuit Evaluation Noise grows during homomorphic evaluation
8. 32:23Multi-Key Version of GSW
9. 35:44Ciphertext Expansion
10. 44:23Distributed Decryption
11. 50:15Spooky FHE: 2 to N parties

" related talks

• 28mTwo Round MPC via Multi-Key FHEDaniel Wichs · Securing Computation (Simons Institute, June 2015)
• 45mFully Homomorphic Encryption IShai Halevi · Cryptography Boot Camp 2015
• 01h 04mFully Homomorphic Encryption IIShai Halevi · Cryptography Boot Camp 2015
• 54mFully Homomorphic EncryptionZvika Brakerski · The Mathematics of Modern Cryptography
• 23mBootstrapping Homomorphic Encryption via Functional EncryptionNir Bitansky, Tomer Solomon · ITCS 2023
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 47mHomomorphic EncryptionMarc Joye, Tabitha Ogilvie · RSA Conference 2024
• 40mIt’s a Kind Of Magic: Computation on CiphertextsMaarten Everts · GOTO Amsterdam 2023