# Zero Knowledge Proof for Correctness of the product of additive ElGamal Ciphers [duplicate]

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.

• 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