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>