> Ultimately what we get is the following theorem. If there exists any Verifier computer program that successfully extracts information by interactively running this protocol with some Prover, then we can simply use the rewinding trick on that program to commit to a random solution, then 'trick' the Verifier by rewinding its execution whenever we can't answer its challenge correctly. The same logic holds as we gave above: if such a Verifier succeeds in extracting information after running the real protocol, then it should be able to extract the same amount of information from the simulated, rewinding-based protocol. But since there's no information going into the simulated protocol, there's no information to extract. Thus the information the Verifier can extract must always be zero.
This seems to identify a way of showing that some protocol is zero-knowledge. But, as I read the paragraph, the requirements aren't strict enough.
Imagine a closely-related protocol, where I get to challenge two edges at once and the four (or three, I guess) incident vertices are revealed. Obviously, I can successfully extract the full 3-coloring through repeated runs of this protocol (revealing four vertices when there are only three legal colors means I can identify which vertices are the same color as which other vertices; given a bounded number of challenges, I can get them all). Also obviously, you can use a time machine to pass any particular challenge in this protocol almost as easily as you can use one to pass the less leaky one-edge challenges.
But I don't see what's making the difference, or how the "theorem" helps me distinguish the protocols. The OP identifies three properties that a zero-knowledge protocol must have: 1, if the prover has a solution, I become confident that it's real; 2, if the prover doesn't have a solution, I become confident that they don't; and 3, zero-knowledgeness.
So, if I'm an honest verifier with no memory (except for previous challenge pass/fail results), the two-edge challenge protocol has the first two properties, just like the one-edge protocol: I'll quickly gain confidence that a genuine solution is real, and I'll quickly discover that a sham solution is false. If there's a time machine involved, I'll quickly become convinced that the prover has a solution even though they don't, because it's easy to fake three or four vertices being properly colored.
If I'm a nefarious verifier with a memory, I can use the extra information that leaks from the two-edge protocol to recover the full solution if one is given, and I can also use it to eventually discover that a nefarious prover is using a time machine to lie to me (when my own illicit copy of the graph-coloring hits a contradiction). The two-edge protocol doesn't fail the completeness or soundness tests. So it must fail the zero-knowledgeness test. How can I tell that? Does the paragraph I quoted indicate how the two-edge protocol fails zero-knowledgeness?
I agree, the quoted paragraph is not clear. It seems to me that the Verifier could not be tricked even using the rewinding trick if it was allowed to use its memory (internal copy of the graph-coloring).
Well, in the protocol described in the OP, the verifier can't build an internal copy of the graph-coloring, because knowing that two adjacent vertices in the graph are two different colors doesn't help anything; that much is required of any solution. In the protocol I describe, the verifier can do that, because revealing more than two vertices simultaneously leaks information that isn't necessarily true of all possible solutions (at least, it can; if three vertices which connect in a triangle turn out to be three different colors, you haven't learned anything because any valid solution will have that property).
The problem I'm having is that I agree that the one-edge protocol is zero-knowledge (and that a verifier could be tricked indefinitely by a prover with a time machine), and obviously the two-edge protocol isn't zero-knowledge (and, in probably-related-but-I'm-not-sure news), a verifier using the two-edge protocol cannot be tricked indefinitely by a time machine). I can tell that, but I tell it by looking within my soul and thinking "yes, there is no information leak when one edge is revealed, but there is a leak when two edges are revealed". That's not a reliable method; I'd like to know how to prove that information does not leak through a protocol, and I don't see that anywhere in the OP.
Roughly speaking, the question here is: can you simulate a multi-edge protocol. That is, can you achieve the following properties using rewinding:
1. The 'fake Prover' simulating the protocol has no knowledge of an actual graph coloring.
2. From the Verifier's PoV, the distribution of the simulated (rewinding-based & fake) protocol transcript is identical to that of a real protocol run where the Prover really does a solution.
3. The simulation still requires only time polynomial in the problem instance (when you include all the rewinding trips).
I think if you follow this through you'll find that simulating a multi-edge protocol that 'looks like' a real transcript is highly challenging.
The reason for condition (3) is to rule out an obvious hack wherein the simulation takes so long that the 'fake Prover' can simply find solve the problem (e.g., by finding a graph coloring in an exponential number of time steps).
etc. etc, then simulating a two-edge protocol is, while more time-consuming than simulating a one-edge protocol, still pretty easy. If the record looks like
Trial 1: PASS (v1 red -- v2 green, v3 green -- v4 blue)
Trial 2: PASS (v1 blue -- v2 red, v7 blue -- v9 red)
Trial 3: PASS (v1 green -- v2 red, v7 green -- v4 red)
then after Trial 3 you can tell that the prover is cheating. The fake trials seem to achieve your properties (1) and (3). I guess they violate #2? What is the "distribution" of a simulated transcript?
Sorry my reply wasn't clear, I understood the question you were asking in your original comment. I was actually referring to your 2-edge protocol when I wrote that it seems the Verifier could not be tricked even in the simulated protocol (since it could detect inconsistencies as you mentioned).
I think the theorem says that if your Solver can successfully trick the Verifier in the simulated protocol (aka using the rewinding trick), then your protocol is zero-knowledge. But I'm really not sure... Let me know if you find a more satisfying answer.
> Ultimately what we get is the following theorem. If there exists any Verifier computer program that successfully extracts information by interactively running this protocol with some Prover, then we can simply use the rewinding trick on that program to commit to a random solution, then 'trick' the Verifier by rewinding its execution whenever we can't answer its challenge correctly. The same logic holds as we gave above: if such a Verifier succeeds in extracting information after running the real protocol, then it should be able to extract the same amount of information from the simulated, rewinding-based protocol. But since there's no information going into the simulated protocol, there's no information to extract. Thus the information the Verifier can extract must always be zero.
This seems to identify a way of showing that some protocol is zero-knowledge. But, as I read the paragraph, the requirements aren't strict enough.
Imagine a closely-related protocol, where I get to challenge two edges at once and the four (or three, I guess) incident vertices are revealed. Obviously, I can successfully extract the full 3-coloring through repeated runs of this protocol (revealing four vertices when there are only three legal colors means I can identify which vertices are the same color as which other vertices; given a bounded number of challenges, I can get them all). Also obviously, you can use a time machine to pass any particular challenge in this protocol almost as easily as you can use one to pass the less leaky one-edge challenges.
But I don't see what's making the difference, or how the "theorem" helps me distinguish the protocols. The OP identifies three properties that a zero-knowledge protocol must have: 1, if the prover has a solution, I become confident that it's real; 2, if the prover doesn't have a solution, I become confident that they don't; and 3, zero-knowledgeness.
So, if I'm an honest verifier with no memory (except for previous challenge pass/fail results), the two-edge challenge protocol has the first two properties, just like the one-edge protocol: I'll quickly gain confidence that a genuine solution is real, and I'll quickly discover that a sham solution is false. If there's a time machine involved, I'll quickly become convinced that the prover has a solution even though they don't, because it's easy to fake three or four vertices being properly colored.
If I'm a nefarious verifier with a memory, I can use the extra information that leaks from the two-edge protocol to recover the full solution if one is given, and I can also use it to eventually discover that a nefarious prover is using a time machine to lie to me (when my own illicit copy of the graph-coloring hits a contradiction). The two-edge protocol doesn't fail the completeness or soundness tests. So it must fail the zero-knowledgeness test. How can I tell that? Does the paragraph I quoted indicate how the two-edge protocol fails zero-knowledgeness?