DDH ⇒ Multiplicatively homomorphic encryption

Fully-black-box reduction · standard model · ElGamal85, TY98 · security loss: tight: one oracle call, advantage-preserving

Statement

The ElGamal scheme of ElGamal85 over $(\mathbb{G},g,p)\leftarrow \mathsf{GrGen}(1^{\lambda })$, with $\mathsf{pk}=y=g^x$ and $\mathsf{Enc}(\mathsf{pk},m;r)=(g^r,m\cdot y^r)$ for $m\in \mathbb{G}$, is multiplicatively homomorphic: the componentwise product of encryptions of $m_1$ and $m_2$ is distributed exactly as a fresh encryption of $m_1{m}_2$ — standard. It is semantically secure iff DDH is hard for $\mathsf{GrGen}$ — TY98.

Sketch

$(g^{r_1},m_1{y}^{r_1})\cdot (g^{r_2},m_2{y}^{r_2})=(g^{r_1+r_2},m_1{m}_2\cdot y^{r_1+r_2})$, and $r_1+r_2\mathrm{mod}p$ is uniform in ${\mathbb{Z}}_p$ when $r_1$ is. CPA security is the reduction on DDH ⇒ PKE: on DDH challenge $(X,Y,Z)$ set $\mathsf{pk}=X$ and answer the challenge query with $(Y,m_b\cdot Z)$.

Notes

• ElGamal85 predates the DDH assumption; the DDH-based CPA proof is later — TY98.