Interactive zero knowledge 3-colorability demonstration
1–10 of 25 posts
Re: Interactive zero knowledge 3-colorability demonstration
#2I can press reveal to make sure the prover is being honest in this simulation, but how would I know that in the real protocol? By the edges alone I can't tell whether or not it's randomly assigning different colors.
Re: Interactive zero knowledge 3-colorability demonstration
#3I can press reveal to make sure the prover is being honest in this simulation, but how would I know that in the real protocol? By the edges alone I can't tell whether or not it's randomly assigning different colors.
I think you need a way for the prover to commit to the colors of every vertex before you choose which edge you want revealed.
Re: Interactive zero knowledge 3-colorability demonstration
#4I can press reveal to make sure the prover is being honest in this simulation, but how would I know that in the real protocol? By the edges alone I can't tell whether or not it's randomly assigning different colors.
The part not shown well here is that before your choice, you would receive a "commitment" for each vertex color in the graph for each iteration. The commitment allows the prover to provide a coloring that can't be changed after the round starts, but also where only the values for the chosen edge will have their commitment "opened".
If each round gets you an edge with different colors for each vertex, you can be confident it was able to 3-color the graph. You have the commitments, so the prover can't change the colors based on your requested edge, so if they didn't color it correctly you know there's some probability of getting one of the edge(s) where it had to give both vertices the same color. You can never be 100% sure it didn't lie and then get lucky each round, but you can do enough rounds to reach whatever probability of that makes you satisfied that it's honest.
Re: Interactive zero knowledge 3-colorability demonstration
#5I can press reveal to make sure the prover is being honest in this simulation, but how would I know that in the real protocol? By the edges alone I can't tell whether or not it's randomly assigning different colors.
I think you need a way for the prover to commit to the colors of every vertex before you choose which edge you want revealed.
Yeah, that's exactly what you need to keep it more honest. This demo doesn't really show that part of the protocol.
Re: Interactive zero knowledge 3-colorability demonstration
#6I can press reveal to make sure the prover is being honest in this simulation, but how would I know that in the real protocol? By the edges alone I can't tell whether or not it's randomly assigning different colors.
This demonstration is utter nonsense, because it's musing a critical step. By the automorphism of color permutations, all possible non-trivial reaponses are equivalent and prove nothing.
What's missing is that the prover has to send you something like a salted hash of every edge coloring (called a "cryptographic commitment") in advance, so that you can verify that the revealed coloring matches what was already committed.
But since the number of distinct single edge colorings is tiny (6), you could crack the hash easily, so you need a fancier commitment protocol than just a hash, perhaps some sort of mutually trusted hashing oracle that only lets you send one query per proof.
Re: Interactive zero knowledge 3-colorability demonstration
#7I can press reveal to make sure the prover is being honest in this simulation, but how would I know that in the real protocol? By the edges alone I can't tell whether or not it's randomly assigning different colors.
The part not shown well here is that before your choice, you would receive a "commitment" for each vertex color in the graph for each iteration. The commitment allows the prover to provide a coloring that can't be changed after the round starts, but also where only the values for the chosen edge will have their commitment "opened". If each round gets you an edge with different colors for each vertex, you can be confi…
What form could such a commitment take over the wire?
Re: Interactive zero knowledge 3-colorability demonstration
#8With the second graph, Turbo mode often gets up to 60% or 70% confidence before detecting an issue. That seems odd, since I'd expect most edges in a graph to be colorable and only a few to have issues, so I'd "expect" most graphs to look fine up to that level. Is this an issue with the confidence equation and prior, or is it just expected that nobody would stop until they hit 99%+ confidence?
In other words, perhaps I'm just asking for the answer to Exercise 2!
Re: Interactive zero knowledge 3-colorability demonstration
#9One thing I do not understand and would like to learn more about is zero-knowledge proofs is that their soundness seems to rest on the data-generating mechanism. Suppose you had an adversary Alice who claims to possess a constructive proof that graph-isomorphism [1] is in P. Secretly, she has proven that graph-isomorphism is NP-complete, but only for a vanishingly small family of graphs, and almost all random graphs are polynomial-time distinguishable. Unless you had prior knowledge of these pathological cases, you never consider sampling graphs from that class, and for every triplet G, K, H, you do propose, Alice will almost surely distinguish the isomorphic pair in polynomial time, despite her claimed proof being incorrect. How would you design a ZKP to test her assertion?
[1]: https://www.scottaaronson.com/papers/philos.pdf#page=37
Re: Interactive zero knowledge 3-colorability demonstration
#10With the second graph, Turbo mode often gets up to 60% or 70% confidence before detecting an issue. That seems odd, since I'd expect most edges in a graph to be colorable and only a few to have issues, so I'd "expect" most graphs to look fine up to that level. Is this an issue with the confidence equation and prior, or is it just expected that nobody would stop until they hit 99%+ confidence? In other words, perhaps…
I suppose if you choose edges at random, then it's as likely to fail early as it is to fail late. So if you get to 70% confidence, that does seem reasonable to believe it's probably 3-colorable (but still with a big chance that it is not).