1
$\begingroup$

I know this topic has been discussed many times on this platform; however, I still lack the intuition behind proof systems' zero-knowledge property.

I understand that goal of the simulator is to simulate the real transcript between the verifier and prover. So if the simulator can create a transcript without having access to the witness that is indistinguishable from real proof by the verifier(it can trick the verifier), we say the proof is zero knowledge.

Here is what doesn't make sense.

Verifier uses the real proof to verify not the simulator-created proof. If the simulated one can trick, how it is related to the real proof? Do simulator has some sort of extra information which real prover doesn't have?

Edit

With the comment I received, my understanding shifted a bit; I would appreaciate it if anyone could tell me it's correct. The intuition is that prover could have generated this transcript using the simulator (as a result, nothing could have been extracted from simulation generated transcript). However, we don't know whether proof actually proves the witness's knowledge, which is "Knowledge soundness" property. Am I correct?

$\endgroup$

2 Answers 2

1
$\begingroup$

A key role in proving that an interactive system has the property of zero knowledge is played by the Simulator (S), which simulates P but does not have access to the witness. His contribution is as follows: V interacts with S. At some point V will put S in the 'difficult position' of not being able to answer a question, as he does not have access to the witness. In this case we return the V movie to a state before the unpleasant question (rewind) and run the protocol from that point onwards. If V (with continuous rewinds) finally accepts S's proof, the protocol has the status of zero knowledge, as V can not distinguish between a P who knows the witness and an S who pretends. That is, V does not export any additional information from the protocol (since in the second case there is no information to export).

Simulator does not have the witness. Simulation of proof in place of P Interacts with V We can not distinguish the interactions ⟨S, V⟩ and ⟨P, V⟩ We also allow rewinds: If at some point V 'asks' something he can not answer S then stop - rewind Zero knowledge if V at some point accepts (even with rewinds) Why: Cannot distinguish P (having witness) from S (not available) As long as S remains PPT Specifically: A V that extracts information from P will extract the same information from S (where there is nothing to export)

$\endgroup$
2
$\begingroup$

In short, the simulator has extra power that the real prover doesn't have.

Suppose Alice wants to prove to me that she is a good sharpshooter. I paint a target on the side of a barn, and make her stand 100m away and shoot it. She hits the bullseye of the target, and I am convinced that she is an excellent sharpshooter.

The "transcript" of this protocol is the permanent record that I take away from the interaction. In this case, it's the side of a barn with a target painted on it, and a bullet hole in the bullseye of the target.

This "protocol" is zero-knowledge because I could have generated the transcript myself. I could have shot a hole in the side of the barn from close range, and then painted a target centered at the hole! When I'm doing this ("simulating" a transcript), I have more power than Alice did during the protocol. I can generate the pieces of the transcript in a different order. I can shoot the barn from closer range than her.

In cryptographic protocols, the simulator always has more power than the real prover. Sometimes the simulator can generate the parts of the transcript in a different order. Sometimes the simulator can "rewind time" -- so the verifier asks a question, and then we rewind time and start the transcript over, knowing what the verifier is going to ask. Sometimes the simulator literally has more computational power than the real prover. Sometimes the simulator has some extra information that the real prover doesn't have (like a trapdoor to some common reference information used in the proof).

$\endgroup$
3
  • $\begingroup$ I appreaciate the answer but I don't know how it answers other questions I had. This only showes an example how simulator has extra power. In fact, to be honest, it confused me. Alice is Prover, you are Verifier... You also simulator. Why would Verifier create itself fake proof (you shooting the target and painting???) $\endgroup$ Dec 11, 2021 at 20:14
  • 1
    $\begingroup$ Simulator is a way of formalizing the following idea: the verifier didn't learn anything because "they could have generated the transcript themselves." $\endgroup$
    – Mikero
    Dec 11, 2021 at 22:18
  • $\begingroup$ I updated my question according to your answer $\endgroup$ Dec 11, 2021 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.