# Proof of correctness of a homomorphic ElGamal sum

Let's suppose we are using the exponential ElGamal as a public-key encryption scheme, so that we encrypt $g^m$ instead of $m$, for some generator $g$. Let $x$ be the private key, and $h=g^x$ be the public key.

We have two parties, and each one of them has a ciphertext encrypted with the same public key: $(R_1,S_1)=(g^{r_1}, g^{m_1} h^{r_1})$ and $(R_2,S_2)=(g^{r_2}, g^{m_2} h^{r_2})$, respectively.

These two parties then gather and perform the homomorphic sum of their ciphertexts by computing the product of their ciphertexts: $(R_3,S_3) = (R_1,S_1) \cdot (R_2, S_2) = (g^{r_1+r_2}, g^{m_1+m_2} h^{r_1+r_2})$.

Is there any way they can prove in zero-knowledge that the sum is correct? That is to say, that $(R_3,S_3)$ is the correct encryption of $m_1+m_2$ without revealing anything else about the addends ($m_1$ and $m_2$ should be kept secret) nor the (plaintext) value $m_1+m_2$?

-
"proof in" $\:\mapsto\:$ "prove in" $\;\;\;$ –  Ricky Demer Aug 29 at 17:22
Are $m_1$ and $m_2$ determined by the original two ciphertexts, or by something else? $\hspace{1.62 in}$ –  Ricky Demer Aug 29 at 17:26
Yes, messages $m_1$ and $m_2$ are encrypted, respectively, in the two original ciphertexts $(R_1,S_1)$ and $(R_2,S_2)$. –  LRM Aug 30 at 8:02
Then D.W.'s answer is completely correct. $\;$ –  Ricky Demer Aug 30 at 8:22
• Each party should publish $(R_1,S_1)$ and $(R_2,S_2)$. They should also publish $(R_3,S_3)$.
• Now anyone can verify that $(R_3,S_3)$ is a correctly-formed encryption of the sum of the messages corresponding to $(R_1,S_1)$ and $(R_2,S_2)$. In fact, there is no need for any fancy zero-knowledge proof: given $(R_1,S_1)$ and $(R_2,S_2)$, anyone who is interested can re-compute $(R_3,S_3)$ on their own and verify that the result they obtained matches what was published.