Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN

Explore a groundbreaking cryptographic construction in this 52-minute conference talk that presents the first somewhat homomorphic encryption schemes for bounded-degree polynomials without relying on lattice assumptions or bilinear maps. Learn how to build these encryption schemes using the sparse learning-parities-with-noise problem combined with assumptions that enable linearly homomorphic encryption, such as decisional Diffie-Hellman or decisional composite residuosity assumptions. Discover how the resulting schemes support an a-priori bounded number of homomorphic operations, specifically o(log λ) multiplications followed by poly(λ) additions, where λ represents the security parameter. Understand the conceptually elegant design where ciphertexts are represented as matrices, with homomorphic addition corresponding to matrix addition and homomorphic multiplication to matrix multiplication, following similar principles to established schemes by Gentry, Sahai, and Waters, as well as Dao, Ishai, Jain, and Lin. Gain insights into this collaborative research published at EUROCRYPT 2025, which advances the field of homomorphic encryption by providing new theoretical foundations and practical constructions for privacy-preserving computation on encrypted data.