In this talk, I will show how to construct somewhat homomorphic encryption from the sparse learning-parities-with-noise problem, along with an assumption that implies linearly homomorphic encryption (e.g., the DDH or DCR 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. Unlike prior somewhat-homomorphic-encryption schemes for bounded-degree polynomials, our new schemes 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, 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 (EUROCRYPT 2025).
Alexandra Henzinger is a Ph.D. student in the Parallel and Distributed Operating Systems group at MIT, advised by Henry Corrigan-Gibbs. Alexandra works on building computer systems that protect their users’ security and privacy. Much of her recent work has focused on private information retrieval, from designing cryptographic protocols to building a private search engine. She has received an NSF GRFP fellowship and an MIT EECS Great Educators fellowship, and she was selected as a 2024 EECS Rising Star.