Additively homomorphic encryption + Sparse LPN ⇒ SHE

Standard model · CHKV25

Statement

If sparse LPN is hard, any linearly homomorphic PKE (additively homomorphic encryption, e.g. from DDH or 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.