Zero knowledge-proof for discrete log that is not honest-verifier

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?

Answer 1

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 $\frac1{\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.

Answer 2

After lots of additional googling I have found some answers:

• These lecture notes, slides 12 through 23; in particular slide 22, which presents a ZK proof of knowledge of five moves;
• This paper by Ronald Cramer, Ivan Damgård and Philip MacKenzie, that presents a ZK proof (p. 365) of four moves.

Denoting the order of the group by p, both of these have knowledge error 2^-p, just like Schnorr.

These (p. 6) and these (p. 5, 6) lecture notes have also been helpful.

Answer 3

This paper of Damgard presents ZKPoK of discrete logarithm in 4 moves: http://www.cs.au.dk/~ivan/Sigma.pdf . The construction is very simple and elegant, just a bit more complex than original Schnorr ptotocol.