Proof of correctness of a homomorphic ElGamal sum

Question

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$?

Answer 1

The question is not very clear about exactly what you want to prove and what is publicly known, but here's my answer, based on my best guess at what you mean:

• 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.