Practical consequences of a honest-verifier zero-knowledge of the Schnorr protocol

Question

Schnorr protocol is known to be honest-verifier zero-knowledge and not perfectly zero-knowledge.

What are the practical consequences of this fact? Does it mean a dishonest verifier can do something to discover the secret exponent $x$?

Setup

• $P$ chooses a large prime $p$ and a generator $g$ of the $q$ order subgroup of $\mathbb Z_p^*$.
• $P$ chooses a secret $x \leftarrow_{uniform} \mathbb Z_q^*$, computes $y = g^x$ and gives $y$ to $V$.

Protocol

• $P$ chooses $r \leftarrow_{uniform} \mathbb Z_q^*$, computes $t = g^r$ and sends $t$ to $V$
• $V$ chooses $c \leftarrow_{uniform} \mathbb Z_q$ and sends it to $P$
• $P$ computes $s = r + cx$ and sends $s$ to $V$
• $V$ verifies that $g^s = ty^c$.

Answer 1

By definition, a dishonest verifier may be able to completely extract the witness from an honest-verifier ZK proof.

To prove this: take any zero-knowledge proof, and add an initial round where the verifier sends 1 to the prover. The prover then works as follows: if it receives 1 then it runs the original zero-knowledge proof; if it receives 0 then it sends the witness.

The above proof is clearly honest-verifier zero-knowledge, but a dishonest verifier can learn the witness by sending 0.

Typically, the point of an honest-verifier zero-knowledge proof is that it can be "compiled" into a (full) zero-knowledge proof without much difficulty.

Having said the above, some honest-verifier zero-knowledge proofs already have stronger properties like witness indistinguishability. This makes no sense for Schnorr itself since there is only one witness, but I believe that the standard Diffie-Hellman tuple sigma protocol is witness indistinguishable (I would want to write a proof to be 100% sure but I'm nearly sure).

Answer 2

There's a strong notion of ZK, which guarantees that no information will be disclosed at all.

As you mentioned, the Schnorr protocol is not full ZK. This means, that a bit of information is leaked with each created transcript. As an example of practical consequence, the protocol loses a property of deniability: now, dishonest verifier, $A$ is able to provide transcripts to third parties and they will be convinced that $A$ communicated with someone who knows $x$ (such verifier could act in the following way: it chooses a challenge always equal to commitment value; as you can see, you can't create a simulator, and ZK could not be satisfied). If this will be used in a composition with other algorithms, for example, if prover $B$ authenticates created transcripts, $A$ is able to show that exactly $B$ knows the secret.

But the most important question, whether the secret could be disclosed by some dishonest verifier? If this is not possible, the protocol is witness hiding (WH).

Easy to see, that if a protocol is ZK, it's WH too. The opposite is not true. So WH is a weaker property than ZK, but it's enough for most applications, and you're asking exactly about WH. It's also important, why WH property could be satisfied with fewer efforts: it can be proved with regards to some complexity assumptions, for example assumption of the hardness of discrete log.

So regarding WH property of Schnorr protocol, the answer - it's not proven (in the standard model, with respect to discrete log assumption), however, no attacks found yet.

However, it's proven in generic group model (GGM) by Victor Schoup (in a similar way he has proved security of discrete log problem and Diffie-Hellman problem against generic algorithms). A proof in GGM, as well as a proof in the random oracle model (ROM) is considered good arguments for security, but not full guarantees. That's because you don't use generic groups or random oracles in practice. You substitute them with something practical and close to ideal, but still not ideal (e.g. elliptic points group instead of the generic group).

WH property of Schnorr protocol was also proved under non-standard "one more discrete log" (OMDL) assumption. Regarding desired proof under plain discrete log assumption, there's even a paper which (pretty paradoxically) proves that no such proof could be found! But still doesn't provide you with any attacks :).

To sum up:

• Full ZK property is indeed missed, but it's very strong property, and for security, against secret recovery, we would be satisfied with weaker WH property.
• WH property of Schnorr protocol is not fully proved, but there are pretty good arguments for it: proven security against generic group algorithms (GGM model), under OMDL assumption.
• At least, no attacks to WH of Schnorr protocol was found yet.
• So, you should not be bothered by secret recovery. But, as a practical consequence of lack of ZK, you have a lack of "deniability".

Answer 3

The question is about consequences of definitions. Schnorr protocol is only somewhat relevant here, serving as the well-known case.

Honest verifier zero knowledge requires indistinguishability of transcripts that have the same challenge of verifier. Consequence is, transcript distribution does not include random choices of verifier, resulting in "easier", less demanding requirements for simulator algorithm. This is completely irrelevant for discovering witness (secret).