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

• The DDH instance of Additively homomorphic encryption + Sparse LPN ⇒ SHE: DDH supplies the linearly homomorphic PKE — CHKV25.