How can a verifier benefit from being malicious or dishonest in a Zero Knowledge interactive proof?

user93353

3/10/24, 8:40 AM

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?

360

1 + 0

zero-knowledge-proofs

zero-knowledge

Score:5

Crypto

Geoffroy Couteau

3/10/24, 9:14 AM

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.

+ 0

Elon Musk

I sit in a Tesla and translated this thread with Ai:

EN: How can a verifier benefit from being malicious or dishonest in a Zero Knowledge interactive proof?

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.