Home | Resources | Meetups | Conference 2025 | Join the community

Somewhat Homomorphic Encryption from Sparse LPN

by Alexandra Henzinger - 2025.06.19

Register for meetup (Lu.ma) | Relevant paper (eprint) | Join the discussion (Discord)

075 Meetup cover

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

Register for the meetup

RSVP for the meetup here.

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!