# Non interactive ZKP that encrypted additive elgamal message is in set of valid messages

Votes are encrypted using the additive variant of ElGamal. I am also using ECElgamal. The idea is that to vote for a particular candidate, you set your message as one of the following $v$ calculated below.

One problem is that if the voter sends a vote not specified in the valid set of $v$'s, then the resulting sum of $v$'s would affect the tallying of votes. For example, if you vote using $2\times2^0$, you are able to vote to candidate 1 $2$ times which not ideal. Or $2\times2^m$ to vote for candidate 2 twice.

How would one verify that the vote that is recorded (which is encrypted) is in one of the valid $v_i$ without decrypting the ciphertext of the vote or showing $v_i$?

The standard solution is to use a proof of encryption of zero, coupled with an or proof and a careful choice of ciphertexts.

A proof of encryption of zero is a proof that the decryption of a ciphertext is zero. For ElGamal, this is typically done using a proof of equal discrete logarithm. Recall that an encryption of zero is of the form $(x,w) = (g^r, y^r g^0)$, where $y$ is the public encryption key, so all you need to prove is that $\log_g x = \log_y w$. (This equality of d.log. proof is standard, I believe it is called Chaum-Pedersen or something. It essentially amounts to a Schnorr proof in a carefully chosen group.)

An or proof allows you to prove that one out of several claims is true. In this case, we consider the claims that several different ciphertexts are encryptions of zero, though only one will be. (Again, this is a standard technique for sigma protocols, which the above proof of encryption of zero is. It dates back to the 90s.)

Now, which ciphertexts do you apply the or proof to? You want to prove that $(x,w)$ is an encryption of $v_1$, $v_2$, ..., or $v_L$? Then you apply the or proof to the ciphertexts $(x,w g^{-v_1})$, ..., $(x, wg^{-v_L})$. If the encryption is valid, one of them will be an encryption of zero, allowing you to complete the or proof.

• This check will also check that it is encrypted using the same public key? – iH8WorkingWith.NetGraphics May 20 '18 at 2:59
• How many proofs does the prover need to do give the verifier? Would the equal to the number of candidates? – iH8WorkingWith.NetGraphics May 20 '18 at 5:09
• Wouldn't the $(x, wg^(-v_L))$ the encrypts to zero gives you the original $v$? – iH8WorkingWith.NetGraphics May 21 '18 at 6:11
• One of the ciphertexts $(x,wg^{-i})$ will be an encryption of zero. But the or proof hides which one is an encryption of zero. – K.G. May 21 '18 at 8:45
• @K.G.Would you know where I could find some detailed explanation on how to implement the protocol you described? Thanks – smax Dec 20 '18 at 22:24