# Zero-Knowledge Challenge-Responce Protocol

Good day to everyone.

I am trying to implement an e voting system (just for reference -it is not important though-it is described at the Internet Voting Protocol Based on Improved Implicit Security by Abhishek Parakh & Subhash Kak Version of record first published: 29 Jun 2010. ).

The protocol I am trying to implement mentions that "The Polling Station verifies the validity of Voter-id by conducting a zero-knowledge challenge-response protocol with the Registry Authority to validate the signature of voter-id."

I have searched at Google, and at Wikipedia about this protocol, but I didn't get much information. It is very important for me, to learn about what is this protocol, and what Polling station has to sent to Registry Authority, and what Registry Authority has to send back. Basically, I need to know how I can achieve to validate the voter-id.

Thank you very much for your time.

Ps. I just created account at this forum. If you need to provide you with any further information please ask it, and I will answer.

-
I did not have a look at the paper you mentioned but in e-voting a voter usually gets something like an authentication token or a one-way signing key signed by an authority. For privacy reasons these signatures are often blinded. –  Thomas Lieven Mar 4 '13 at 16:47
Thank you very much Mr Thomas. I also use this one-way hashed sign key for the voter to vote. The problem I have is when the e-voting authorities communicate (the polling station and the registry authority, because they have to communicate using the zero-knowledge challenge-response protocol). Thank you very much for your time :))) –  Andreas Mar 4 '13 at 18:31
I'm sorry but I still don't get why you need this ZK protocol or what it exactly is supposed to do. If an authority signs the one-way-key the voter gets the signature as well as the certificate of the signing key for verification. The voter now sends the polling station his vote, his signed public one-way-key and the certificate. Based on a PKI the polling station is now able to verify the authority's signature. There is no need to contact the authority. –  Thomas Lieven Mar 5 '13 at 16:15
have you checked heliosvoting.org ? they use partial homomorphic techniques –  sashank Mar 6 '13 at 6:21

Reading the original paper, I figure out the question. This voting scheme employed the well-known undeniable signature scheme, proposed by Chaum and Van Antwerpen in 1989 (or Chaum 1990 or Chaum and Van Antwerpen 1991).

• KeyGen: The RA is a signer and has a public key $X = g^x$ and a secret key $x$
• Sign: For a message $m \in \mathbb{G} = \mathbb{Z}_p$, the signature is $\sigma = m^x \in \mathbb{G}$. (In your case, $m = r_{id}$.)
• Cofirmation: The verifier (the polling station) and the signer (the RA) interacts to verify a token $(r_{id},\sigma)$ from a voter is correct or not.

In confirmation, the RA proves that $\log_g(X) = \log_{r_{id}}(\sigma)$. You can find the standard $\Sigma$ protocol for this confirmation, say, the $\Sigma$ protocol for the DDH language.

You can find the $\Sigma$ protocol for the DDH language in the lecture notes available at the web.

-
Thank you very much for your reply, and for reading the paper. To be honest I am speaking for the voting phase (2nd phase). But what is this standard Σ protocol and the DDH language? I searched them, but I did not find something which can be helpful... –  Andreas Mar 8 '13 at 15:48
My answer referred to the same point. As you know, r_{id} is the voter's identity. The polling station has (g,g^x,r_{id},\sigma) and the RA has x. If \sigma = r_{id}^x, then the RA can prove that (g,g^x,r,\sigma) is the DDH tuple. –  xagawa Mar 10 '13 at 13:43
Thank you very much. But what is this standard Σ protocol and the DDH language? I did not understood... –  Andreas Mar 12 '13 at 14:58
Why don't you google with the keywords, say, "Sigma, DDH, Zero-Knowledge"? I found a nice lecture note written by Berry Schoenmakers. –  xagawa Mar 13 '13 at 15:56

Unfortunately, you are probably not going to be able to fill in the missing details, unless you have a great deal of crypto experience (which it sounds like you don't have).

You could start by reading about zero-knowledge proofs. There's a lot of information on that subject available. You will need to know it before you can progress. It sounds like you are saying that the paper does not specify the particular zero-knowledge proof protocol to use; they just claim that it's possible to invent one. Therefore, to fill in the missing details, apparently you're going to have to invent the zero-knowledge proof protocol. That requires quite a bit of knowledge and experience with zero-knowledge proofs.

In practice, it's probably not realistic to think that you're going to be able to teach yourself this in a reasonable time frame. Therefore, I think you should give up on trying to implement this protocol. It sounds like the protocol is not fully specified, and thus is not really ready to be implemented. If the protocol is not fully specified, that's probably a pretty good hint that this is not ready for practical deployment, and implementing it is going to be beyond the reach of all but an expert in the area.

-