I've came across a Stackexchange question about the Chaum-Pedersen Protocol which is based on the generalised schnorr protocol. As I understand it, it uses discrete logs and cyclic groups of prime order q to prove knowledge of a secret value x, which in this scenario is an equality proof for the discrete log.

The paper referred to in the question is https://www.cs.umd.edu/~waa/414-F11/IntroToCrypto.pdf, where there is more information and context about the protocol in the first section of page 377, paragraph 3.2.

I've implemented the protocol in python so far to check if it works. When the calculation s = k - c * x (mod q) happens, my script produces unsuccessful authentication outputs when c * x > k. I use the right modulo (not rem) so it's not a wrong operator problem due to possible negative numbers.

I've read the first answer on Stackoverflow and changed it accordingly. Now it works. 

What I don't understand is: Why does the answer introduce a new variable/prime number p? Neither the section in the paper, nor the specified applied protocol image from Stackexchange mentioned such an additional prime number. There is also no mention of mod operations on the values with this number p.


1 Answer 1


The Chaum-Pedersen protocol works for any cyclic group of order $q$ for which the discrete logarithm problem is hard. There are various groups that we could use here though the most common choices are multiplicative groups modulo primes and elliptic curve groups. The SE answer has chosen the former as an illustrative example as it is easier for those with less mathematical experience to understand than elliptic curve groups.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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