Score:1

Simulator vs Prover -- Zero Knowledge Property

tv flag

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?

Score:2
us flag

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).

tv flag
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???)
us flag
Simulator is a way of formalizing the following idea: the verifier didn't learn anything because "they could have generated the transcript themselves."
tv flag
I updated my question according to your answer
Score:1
sd flag

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)

mangohost

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.