Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I want to implement Threshold Elgamal as described in section 6.3.1 and in the decryption phase each party must broadcast a sigma proof to show that it actually has a valid secret share of the secret key.

I read about Schnorr protocol as a solution for sigma proof but it is said to be insecure, in chapter 5 of the same lecture notes.

What secure sigma proof could I use ?

It would be great if the sigma proof is non-interactive.

share|improve this question
up vote 7 down vote accepted

Sigma protocols as-is are secure only for honest verifiers. However, they can be easily compiled into full-blown zero knowledge protocols. If you don't want interaction, then the Fiat-Shamir transform suffices, with security in the random oracle model. With interaction, you can do the transform at little cost using commitments based on DDH. For more information on this, you can see this video. If you have Springer Online access, then you can also see this chapter. If you don't have access, then send me an email and I'll send you the chapter.

share|improve this answer

I guess you are talking about Figure 5.3?

It is said that the Schnorr proof (sigma protocol for discrete log relation) is insecure against cheating verifiers - it is only honest-verifier zero knowledge. Sigma protocols are always only defined in the honest-verifier zero-knowledge setting.

To see why a cheating verifier is a problem in Figure 5.3 think about what happens if a cheating verifier sends $c:=0$ to the prover. How does $r$ then look like? Is this a problem for zero-knowledge (when one needs to come up with a simulator that does not know the witness)?

Now you can turn any sigma protocol into a non-interactive zero-knowledge proof in the random oracle model using Fiat-Shamir (basically, compute the challenge $c$ as a hash of the first message $a$). Then you obtain perfect zero-knowledge (no longer honest-verifier) and you no longer have to worry about cheating verifiers (if you can live with the random oracle assumption).

For the mentioned threshold ElGamal protocol you need a sigma protocol for equality of discrete logarithms (see Figure 5.7 of the lecture notes).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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