Several texts talk about malicious/dishonest verifiers in a zero-knowledge interactive proof but none of them properly detail how a dishonest verifier can gain extra knowledge over an honest verifier using some examples like "Quadratic Residue Interactive proof" or "graph 3 colouring Interactive proof".

I went over the proofs for these 2 examples for honest verifier where obviously no knowledge is gained, but I am unable to figure out who this breaks if the verifier were dishonest. I assume by dishonest, it means a verifier who doesn't use a random number where he is supposed to or is my assumption wrong?

For e.g. in the QR proof, the verifier is supposed to pick a random bit & send it to the prover - but let's say he doesn't pick a random bit but always sends 0 or always sends 1 - how does this give him any extra info in any way?


1 Answer 1


For many concrete HVZK proof systems, we actually don't have an attack against zero-knowledge when the verifier is dishonest - but we don't have a security proof either!

In particular, in many $\Sigma$-protocols, such as the standard QR argument, this is the case. We only know how to prove HVZK, but we don't have an explicit attack against zero-knowledge.

If you've not done it, I suggest that you run through the security analysis and try to understand why it breaks down when the verifier can be malicious. The issue will not appear when the verifier does something too simple, like always sending zero, but it appears as soon as the verifier picks their challenge based on the first flow (e.g. by hashing the first flow).

Still, the fact that we have not found an explicit attack should not be taken as a strong support for the assumption that the protocol is secure. There are many examples of protocols for which we had no attacks for years, and the protocol sure looked secure (but we had no proof) -- and eventually, an explicit attack was found.


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.