One 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?<p>[1]: <a href="https://www.scottaaronson.com/papers/philos.pdf#page=37" rel="nofollow">https://www.scottaaronson.com/papers/philos.pdf#page=37</a>
With 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?<p>In other words, perhaps I'm just asking for the answer to Exercise 2!
I 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.
Oddly, YouTube recommended me a Numberphile video about this a couple of days ago - "Zero Knowledge Proof (Avi Wigderson)" from Feb 2021. Covers the same kind of ground although extended to "you can turn any proof into a 3 colour graph and use that in your zero knowledge proof" areas (in which I am completely bereft of knowledge.)<p><a href="https://www.youtube.com/watch?v=5ovdoxnfFVc" rel="nofollow">https://www.youtube.com/watch?v=5ovdoxnfFVc</a>