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

BibTeX

Copy

@Inproceedings{EC:CHKV25,
  author = {Henry {Corrigan-Gibbs} and Alexandra Henzinger and Yael Tauman Kalai and Vinod Vaikuntanathan},
  title = {Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse {LPN}},
  pages = {3--33},
  editor = {Serge Fehr and Pierre-Alain Fouque},
  booktitle = {Advances in Cryptology -- {EUROCRYPT}~2025, Part~II},
  volume = {15602},
  series = {Lecture Notes in Computer Science},
  address = {Madrid, Spain},
  month = {may~4--8},
  publisher = {Springer, Cham, Switzerland},
  year = {2025},
  doi = {10.1007/978-3-031-91124-8_1},
}