Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question
    
"proof in" $\:\mapsto\:$ "prove in" $\;\;\;$ –  Ricky Demer Aug 29 '13 at 17:22
1  
Are $m_1$ and $m_2$ determined by the original two ciphertexts, or by something else? $\hspace{1.62 in}$ –  Ricky Demer Aug 29 '13 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 '13 at 8:02
    
Then D.W.'s answer is completely correct. $\;$ –  Ricky Demer Aug 30 '13 at 8:22

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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