Abstract

In this talk, we will construct somewhat homomorphic encryption from the sparse learning-parities-with-noise problem, along with an assumption that implies linearly homomorphic encryption (e.g., the decisional Diffie-Hellman or decisional composite residuosity assumptions). The resulting schemes support an a-priori bounded number of homomorphic operations: o(\log \lambda) multiplications followed by poly(\lambda) additions, where \lambda is a security parameter. This gives the first constructions of somewhat homomorphic encryption for the class of bounded-degree polynomials that do not rely on lattice assumptions or bilinear maps. Moreover, our schemes are conceptually simple: much as in Gentry, Sahai, and Waters’ fully homomorphic encryption scheme and in Dao, Ishai, Jain, and Lin’s homomorphic secret-sharing scheme, ciphertexts in our scheme are matrices, homomorphic addition is matrix addition, and homomorphic multiplication is matrix multiplication.

Joint work with Henry Corrigan-Gibbs, Yael Kalai, and Vinod Vaikuntanathan (published at EUROCRYPT 2025).