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.

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Mar 19, 2014 at 21:40

1 Answer 1


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 https://crypto.stackexchange.com/a/13240/351).

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.


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