Take a cyclic group of prime order. The Schnorr-protocol for proving knowledge o

Question

Take a cyclic group of prime order. The Schnorr-protocol for proving knowledge of the discrete logarithm of some group element is honest-verifier zero-knowledge, meaning that if the verifier chooses his challenge randomly, then he learns nothing about the log.

However, I'm looking for a zero-knowledge proof of knowledge of discrete logs that is not honest-verifier zero-knowledge; I want it (and particularly the simulator) to be able to deal with any verifier, honest or not. Preferably as efficient as possible, on the prover's side. My Google-fu seems to have deserted me; does anyone have any pointers?

Explanation / Answer

There are two answers. One, go non-interactive with the Fiat-Shamir transform. This requires the Random Oracle Model (ROM) to analyse, but the ROM is standard enough in cryptography and ROM proofs have been used in practice for long enough that this shouldn't worry you. It gets you full ZK, curiously enough for the exact same reason that plain Schnorr is only HVZK.

Another answer is to reduce the size of the challenge space from p (the group order) to log(p). This gets you full ZK, but your soundness error drops to 1/log(p) too so you have to repeat the whole protocol O(log(p)) times to get the same soundness as one HVZK Schnorr execution. This repetition doesn't destroy your ZK property however.

Jan Camenisch's work contains a good description of these issues if I remember well.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.