DDH + Sparse Learning Parity with Noise ⇒ Somewhat homomorphic encryption (SHE)

Standard model · CHKV25

Statement

If DDH and sparse LPN are both hard, there is 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.

Notes

• DDH gives a linearly homomorphic PKE, exponential ElGamal, which decrypts only small messages and so is not additively homomorphic; the construction needs only linear homomorphism — CHKV25.