Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN

on YouTube ↗52m

" summary

Construction claims somewhat homomorphic encryption from sparse LPN plus a standard assumption that yields linearly homomorphic encryption (e.g., DDH or DCR), avoiding lattices and pairings. Ciphertexts are matrices as ciphertexts with homomorphic addition = matrix addition and multiplication = matrix multiplication; decrypting is a cheap linear function. Scheme supports o(log λ) multiplications followed by poly(λ) additions over Fq, needs a large evaluation key (stored once) but the construction and security proofs appear to work (EUROCRYPT 2025 paper).

AI-written summary · about

" chapters (11)

1. 0:00Introduction
2. 3:01Homomorphic encryption spectrum
3. 6:13Motivation for new HE assumptions
4. 8:23Sparse LPN overview
5. 14:26Homomorphic ops with sparse LPN
6. 27:19Non-compact ciphertexts challenge
7. 31:36Sparse LPN with linear HE
8. 37:12Final construction and key eval
9. 40:30Efficiency and assumptions open questions
10. 43:19Approaches to achieve fully homomorphic encryption
11. 51:00Q&A

" related talks

• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020
• 45mFully Homomorphic Encryption IShai Halevi · Cryptography Boot Camp 2015
• 01h 06mOn the Assumptions Used for ObfuscationBenny Applebaum · Simons Institute Workshop: New Developments in Obfuscation
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 26mObfuscation 1Amit Sahai · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 53mLPN Based IO Part 2Rachel Lin · Simons Institute Workshop: New Developments in Obfuscation
• 57mTutorial: Encrypted Computation from LatticesHoeteck Wee · Lattices: New Cryptographic Capabilities 2020
• 54mFully Homomorphic EncryptionZvika Brakerski · The Mathematics of Modern Cryptography