For related materials I read, it seems that for the public-coin setting, the verifier will always send random messages to the prover. In this setting, can we regard the verifier as an honest verifier, since he always replies with a random message (rather than a message depends on previous messages)?

In [GK'91], it is proved that suppose that $L$ has a constant-round, negligible error, public-coin black-box ZKproof. Then $L \in BPP$. This theorem confuses me a lot.

For example, for Schnorr's protocol, we know that it is special honest-verifier zero-knowledge. But according to [GK'91], it seems that the protocol is not public-coin zero-knowledge (except DLOG is in $BPP$). Therefore, it seems that we cannot treat public-coin settings as honest-verifier settings. But what is the difference between public-coin and honest-verifier?

I am sorry that maybe I misunderstood some related definitions. Could anyone help me with this question?


1 Answer 1


In this setting, can we regard the verifier as an honest verifier, since he always replies with a random message (rather than a message depends on previous messages)?

No. In a public coin protocol the honest verifier will always send random coins as their messages. A malicious verifier is under no obligation to do so. They can choose whichever message makes the simulator's life the hardest.

Imagine some public coin zero-knowledge proof protocol where the length of verifier messages is at least linear in the security parameter. We can modify this protocol so that the prover does something stupid (say send the witness) in response to a very small number (say just one) of possible verifier messages.

In the honest verifier case this is not an issue because the case only occurs with negligible probability. So the original simulator still works for this modified protocol. I.e., the protocol remains HVZK. But a malicious verifier can just always choose that one bad message, making simulation impossible without being able to efficiently find witnesses.

So there's no contradiction. [GK'91] only applies to ZK proofs, whereas Schnorr is only an HVZK proof.

Additionally one might note, the language you call $\mathsf{DLOG}$ is not in general a hard language. For any cyclic group $(\mathbb{G},\cdot)$¹ of order $q$ generated by $g \in \mathbb{G}$, the language for which Schnorr is an HVZK proof can be defined as follows:

$$\mathsf{DLOG_{\mathbb{G}}}=\{A\in\mathbb{G}\mid \exists x \in \mathbb{Z}_q: g^x=A\}$$

However, since the group is generated by $g$, this is just a very convoluted way of saying $$\mathsf{DLOG_{\mathbb{G}}}=\mathbb{G}.$$

Thus, if group membership can be decided efficiently for $\mathbb{G}$, then this language is not actually a hard language and it would actually hold that $\mathsf{DLOG_{\mathbb{G}}} \in \mathsf{BPP}$. In fact in many cases, it's actually true that $\mathsf{DLOG_{\mathbb{G}}} \in \mathsf{P}$. For example in the case of an elliptic curve over a finite field it is trivial to deterministically decide whether a given point $P$ is on the curve or not by just evaluating the curve equation. Similarly in the safe-prime setting it is easy to check group membership.

The interesting part of Schnorr is not usually that it proves the existence of a discrete log, it's that it's also a proof of knowledge.

¹ Written in multiplicative notation as any sane person would.


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.