Paper 2024/1760

Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN

Henry Corrigan-Gibbs, Massachusetts Institute of Technology
Alexandra Henzinger, Massachusetts Institute of Technology
Yael Kalai, Massachusetts Institute of Technology
Vinod Vaikuntanathan, Massachusetts Institute of Technology
Abstract

We construct somewhat homomorphic encryption schemes from the learning sparse parities with noise (sparse LPN) problem, along with an assumption that implies linearly homomorphic encryption (e.g., the decisional Diffie-Hellman or decisional composite residuosity assumptions). Our resulting schemes support an a-priori bounded number of homomorphic operations: $O(\log \lambda/\log \log \lambda)$ multiplications followed by poly($\lambda$) additions, where $\lambda \in \mathbb{N}$ is a security parameter. These schemes have compact ciphertexts: after homomorphic evaluation, the bit-length of each ciphertext is a fixed polynomial in the security parameter $\lambda$, independent of the number of homomorphic operations applied to it. This gives the first somewhat homomorphic encryption schemes that can evaluate the class of bounded-degree polynomials with a bounded number of monomials without relying on lattice assumptions or bilinear maps. Much like in the Gentry-Sahai-Waters fully homomorphic encryption scheme, ciphertexts in our scheme are matrices, homomorphic addition is matrix addition, and homomorphic multiplication is matrix multiplication. Moreover, when encrypting many messages at once and performing many homomorphic evaluations at once, the bit-length of ciphertexts in some of our schemes (before and after homomorphic evaluation) can be arbitrarily close to the bit-length of the plaintexts. The main limitation of our schemes is that they require a large evaluation key, whose size scales with the complexity of the homomorphic computation performed, though this key can be re-used across any polynomial number of encryptions and evaluations.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Homomorphic Encryption
Contact author(s)
henrycg @ csail mit edu
ahenz @ csail mit edu
tauman @ mit edu
vinodv @ csail mit edu
History
2024-10-30: revised
2024-10-28: received
See all versions
Short URL
https://ia.cr/2024/1760
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/1760,
      author = {Henry Corrigan-Gibbs and Alexandra Henzinger and Yael Kalai and Vinod Vaikuntanathan},
      title = {Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse {LPN}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/1760},
      year = {2024},
      url = {https://eprint.iacr.org/2024/1760}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.