Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question already has an answer here:

Suppose we use Additive ElGamal defined as follows:

Let $(K,E,D)$ be a triple. The key-generator $K$ outputs the description of a finite multiplicative group $G$ of prime order $q$, with three generators $(g,h,f)$ which are set to be the public-key $p_k$ of the system; the secret-key $s_k$ is set to the value $\log_g h$. For a public-key $(g,h,f)$ the encryption function $E(r,x)$ equals the tuple $(g^r, h^r, f^x)$. The operations $+$ and $\oplus$ are defined as addition modulo $q$ and the operation $\otimes$ is defined as point-wise multiplication over $G \times G$. The decryption function is denoted $D$. For a secret key $\log_g(h)$ given $(G,H)$ it returns $H/G^{\log_g(h)}$ and then performs a brute-force search over all possible values for $f^x$ to recover $x$.

So if I have two ElGamal encrypted cipher texts, $c_1= E(r_1,m_1)$ and $c_2 = E(r_2,m_2)$, I can do $c_1 \otimes c_2$ to get the same result as I would get if I did $E(r_1 \oplus r_2, m_1+m_2)$.

Can I somehow construct a zero knowledge proof, that, given a cipertext $c_1$, proves I only added one of $x$ possible ciphers?

Background would be an application for e-voting. Given a set of candidates, I want to prove that I just added one of the valid candidates (predetermined numbers) to the cipher. I already found a ZKP that shows that the Cipher I want to add is well-formed.

share|improve this question

marked as duplicate by D.W., DrLecter, rath, archie, figlesquidge Mar 20 '14 at 23:56

This question was marked as an exact duplicate of an existing question.

I encourage you to put in a bit more effort on formatting the question to be easily readable. Did you know you can use Latex (Mathjax) on this site? See the help center for more. – D.W. Mar 19 '14 at 21:40
up vote 0 down vote accepted

El Gamal can be made additively homomorphic with the techniques shown here: Can Elgamal be made additively homomorphic and how could it be used for E-voting? or additive ElGamal encryption algorithm (see also

If you use the additively homomorphic variant of El Gamal, you don't need any zero knowledge proof. Anyone can verify that the addition was done correctly. See Proof of correctness of a homomorphic ElGamal sum, which shows exactly how.

share|improve this answer

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