Additively homomorphic encryption ⇒ HE

Fully-black-box reduction · standard model · folklore · security loss: none

Statement

An additively homomorphic encryption scheme is a homomorphic encryption scheme for the class of sums of $k$ of its messages, for every $k$, with the same IND-CPA advantage — folklore.

Sketch

$\mathsf{Eval}$ on a sum of $k$ messages applies the binary $\mathsf{Eval}$ $k-1$ times. Each of the $k$ encryptions lies in ${\mathcal{C}}_{\mathsf{pk}}$ and decrypts to its message by perfect correctness; ${\mathcal{C}}_{\mathsf{pk}}$ is closed under the binary $\mathsf{Eval}$ and the homomorphism holds on all of it, so each intermediate ciphertext lies in ${\mathcal{C}}_{\mathsf{pk}}$, has length $\ell (\lambda )$ and decrypts to the partial sum. Since $M\ge 2$, the sum of $k$ messages depends on all $k$ of them.