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$
  • $\begingroup$ "proof in" $\:\mapsto\:$ "prove in" $\;\;\;$ $\endgroup$ – user991 Aug 29 '13 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 '13 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 '13 at 8:02
  • $\begingroup$ Then D.W.'s answer is completely correct. $\;$ $\endgroup$ – user991 Aug 30 '13 at 8:22
5
$\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, privacy policy and cookie policy

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