1
$\begingroup$

I still do not understand the security model when proving the zero-knowledge property.

Take the Sigma protocol as an example:

In the book Proofs, Arguments, and Zero-Knowledge (Section 12.2.1), the definition of the Honest Verifier Perfect Zero-Knowledge property is as follows:

the distribution over transcripts output by the simulator is identical to the distribution over transcripts produced by the honest verifier in the $\sum$ protocol produced by the honest verifier in the $\sum$ protocol interacting with the honest prover.

My confusion is that, to output a valid proof without the witness, the simulator firstly needs to select challenge $e$, sample $z$ (response), and finally compute the corresponding first commitment message $a$. The order of the message has changed.

Does the order of the message matter? I already asked a similar question in Why is the definition of Special-honest verifier zero-knowledge probabilistic?. However, that question focuses on the completeness property.

Improve this question
$\endgroup$
1
  • $\begingroup$ There was an attempt to edit this question by an anonymous user. Thanks for trying to improve the question, but I think that replacing the large sigma with a smaller one is not something we want into our review que; please do not bother with such minor edits until the edit privilege has been awarded to you. $\endgroup$ Commented Nov 18 at 15:54

2 Answers 2

Reset to default
0
$\begingroup$

To understand this, consider what the definition of (perfect) zero-knowledge (or in this case perfect honest verifier zero-knowledge (HVZK) is supposed to model.

The idea is that

Any information the verifier might know after interacting with the prover is information they already knew, without interacting with the prover at all.

Now the question for HVZK is, what information can an honest verifier possibly learn from interacting with the prover? The answer is that the only additional information the honest verifier possesses after interacting with the prover is a transcript of an honest execution of the protocol.

So if the verifier can sample the same (as in distributed identically) transcript by themselves without ever interacting with the prover, that means whatever information they might have extracted from their (honest) interaction with the prover, they can just as easily extract from the simulated transcript. It does not matter how the transcript is sampled, as long as the final distribution is the same.

Improve this answer
$\endgroup$
0
$\begingroup$

Does the order of the message matter?

The order matters. The simulator does not have access to the secret witness that allows the prover to convince the verifier. By the soundness of the protocol, for a fixed commitment $a$, it cannot reply to every challenge $e$. So the easiest way to show zero-knowledge is to fix $e$ in advance such that it can produce a commitment and a response that are consistent with $e$. For example in the protocol for graph 3-coloring, the simulator does not know a 3-coloring of the graph, but if it knows which edge will be opened, it can commit to different colors for the two nodes along that edge.

More generally, if you have a simulator that first produces the commitment $a$, then samples a challenge $e$ and finally computes $z$; and if assume the transcript produced by such a simulator is indistinguishable from a real interaction with the prover; then the existence of such a simulator would imply that the proof system is not sound.

The reason is that that simulator, by using the same ordering of messages as a real interaction, can be used as a cheating prover:

  • Have the simulator output $a$, send that to the verifier and put the simulator on pause.
  • Upon challenge $e$, resume the simulator to get $e'$.
  • If $e\neq e'$, rewind the simulator until $e=e'$.
  • Then continue to get $z$ and send that to the verifier.

Assuming the protocol is perfect or statistical ZK, the challenge $e'$ must be uniform and independent of $a$, so it will hit $e$ eventually (and it not too much time assuming the challenge space is small enough). This contradicts knowledge soundness since the above prover convinces the verifier without knowing a witness.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.