Paper 2024/1760
Somewhat Homomorphic Encryption from Linear Homomorphism and Sparse LPN
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 DiffieHellman or decisional composite residuosity assumptions). Our resulting schemes support an apriori 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 bitlength 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 boundeddegree polynomials with a bounded number of monomials without relying on lattice assumptions or bilinear maps. Much like in the GentrySahaiWaters 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 bitlength of ciphertexts in some of our schemes (before and after homomorphic evaluation) can be arbitrarily close to the bitlength 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 reused across any polynomial number of encryptions and evaluations.
Metadata
 Available format(s)
 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
 20241030: revised
 20241028: received
 See all versions
 Short URL
 https://ia.cr/2024/1760
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/1760, author = {Henry CorriganGibbs 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} }