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

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?

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.

• Thanks for your answer! I was aware of the second way, but I was hoping for something more efficient. By now I've found some answers myself, see the answer below. Apr 12, 2015 at 14:30