Somewhat Homomorphic Encryption from Sparse LPN w/ Alexandra Henzinger

​#Abstract

​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.

​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.Unlike prior somewhat homomorphic encryption schemes for the class of 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 (to appear at EUROCRYPT 2025).

​#About the Speaker

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.

​

#More Information

Want more information, recordings of the presentations, slides, and other resources from the meetup? Visit this meetup's resource page at https://fhe.org/meetups/075

#Never Miss an Update

The newsletter where we post community announcements: https://fheorg.substack.com/

​The discord server where you can discuss FHE related topics with the community: https://discord.fhe.org

​Make sure to join either (or both) of these to stay informed about future events!