4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ "proof in" $\:\mapsto\:$ "prove in" $\;\;\;$ $\endgroup$
    – user991
    Aug 29, 2013 at 17:22
  • 1
    $\begingroup$ Are $m_1$ and $m_2$ determined by the original two ciphertexts, or by something else? $\hspace{1.62 in}$ $\endgroup$
    – user991
    Aug 29, 2013 at 17:26
  • $\begingroup$ Yes, messages $m_1$ and $m_2$ are encrypted, respectively, in the two original ciphertexts $(R_1,S_1)$ and $(R_2,S_2)$. $\endgroup$
    – LRM
    Aug 30, 2013 at 8:02
  • $\begingroup$ Then D.W.'s answer is completely correct. $\;$ $\endgroup$
    – user991
    Aug 30, 2013 at 8:22

1 Answer 1

6
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.