[CHKV25] Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN

Authors: Henry Corrigan-Gibbs, Alexandra Henzinger, Yael Tauman Kalai, Vinod Vaikuntanathan | Venue: Eurocrypt 2025 | Source

Abstract

We construct Somewhat Homomorphic Encryption (SHE) — a scheme supporting $O(\log \lambda /\log \log \lambda )$ homomorphic multiplications followed by polynomially many additions — from two ingredients: the Sparse LPN assumption and any linearly homomorphic public-key encryption scheme (such as one based on DDH or DCR). The construction uses matrix-based ciphertexts where homomorphic addition is matrix addition and homomorphic multiplication is matrix multiplication. This gives the first SHE scheme that does not rely on lattice assumptions or bilinear maps.