Additively homomorphic encryption + Sparse LPN ⇒ SHE

Standard model · CHKV25

Statement

If sparse LPN is hard, any linearly homomorphic PKE, such as an additively homomorphic encryption scheme like Paillier’s from DCR, yields a somewhat homomorphic encryption scheme supporting $O(\log \lambda /\log \log \lambda )$ homomorphic multiplications followed by $\mathrm{poly}(\lambda )$ additions, whose evaluated ciphertexts have bit-length a fixed polynomial in $\lambda$, independent of the number of operations applied — CHKV25.