4 ms·

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

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? [1]: https://www.scottaaronson.com/papers/philos.pdf#page=37 https://www.scottaaronson.com/papers/philos.pdf#page=37

wakamoleguy 5y ago
One difference seems to be in the size of the domain. In the interactive example, you know the possible edges to begin with, and selecting them is straightforward. The confidence is calculated based on that. For graph isomorphism, you would have little confidence that you can pull from the full set of graphs, and so you would have a hard time building confidence. If there is a way around that, I'm genuinely curious as well.
justicz 5y ago
That’s a great question. One idea would be for Alice to generate a machine-checkable proof of her claim (e.g. in Coq or something). Instead of playing the typical game where she distinguishes graphs, we just do a secure two-party computation to check the proof, where Alice’s public input is the claim, and her private input is the proof.
procedurecall 5y ago
You may be interested in Mahaney's Theorem (https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem), which 'answers' a special case of this: If by vanishingly small you mean polynomial size, and you also assume Alice has an algorithm that can distinguish the two subclasses of graph isomorphism, then P=NP if Alice has these facts. By 'distinguish', I specifically mean that Alice has a polynomial time algorithm that will tell you, for an input of graph isomorphism, is it part of a subclass of graph isomorphism which is NP-complete, and which has polynomial size.
- bmc7505 5y ago
  This is useful information, thank you for sharing this theorem! I am still skeptical about the soundness of the verifier's challenge generating mechanism. Assuming P!=NP and the challenge is drawn uniformly from the full space, I am still not convinced that the prover does not have access to a backdoor which makes the challenge "easier" on average than the challenger realizes. Even if challenge instances are superpolynomial in the worst case, empirically, we know from SAT solving competitions that a very small fraction of randomly sampled k-SAT instances are truly hard and most are in P. It is nontrivial to design a challenge whose average case is superpolynomial, and there are many open questions in the field of average-case complexity [1]. I would be very skeptical that the challenge generator is not somehow poisoned. Even if the prover did not collude with the protocol designer to poison it directly, if she can infer any information about the internal state of the verifier from the instances he proposes, she may be able to solve future challenges much more easily than would be possible by random chance. [1]: https://arxiv.org/pdf/cs/0606037.pdf https://arxiv.org/pdf/cs/0606037.pdf

wakamoleguy 5y ago

One difference seems to be in the size of the domain. In the interactive example, you know the possible edges to begin with, and selecting them is straightforward. The confidence is calculated based on that. For graph isomorphism, you would have little confidence that you can pull from the full set of graphs, and so you would have a hard time building confidence. If there is a way around that, I'm genuinely curious as well.

justicz 5y ago

That’s a great question. One idea would be for Alice to generate a machine-checkable proof of her claim (e.g. in Coq or something). Instead of playing the typical game where she distinguishes graphs, we just do a secure two-party computation to check the proof, where Alice’s public input is the claim, and her private input is the proof.

procedurecall 5y ago

You may be interested in Mahaney's Theorem (https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem https://en.m.wikipedia.org/wiki/Mahaney%27s_theorem), which 'answers' a special case of this: If by vanishingly small you mean polynomial size, and you also assume Alice has an algorithm that can distinguish the two subclasses of graph isomorphism, then P=NP if Alice has these facts. By 'distinguish', I specifically mean that Alice has a polynomial time algorithm that will tell you, for an input of graph isomorphism, is it part of a subclass of graph isomorphism which is NP-complete, and which has polynomial size.

bmc7505 5y ago
This is useful information, thank you for sharing this theorem! I am still skeptical about the soundness of the verifier's challenge generating mechanism. Assuming P!=NP and the challenge is drawn uniformly from the full space, I am still not convinced that the prover does not have access to a backdoor which makes the challenge "easier" on average than the challenger realizes. Even if challenge instances are superpolynomial in the worst case, empirically, we know from SAT solving competitions that a very small fraction of randomly sampled k-SAT instances are truly hard and most are in P. It is nontrivial to design a challenge whose average case is superpolynomial, and there are many open questions in the field of average-case complexity [1]. I would be very skeptical that the challenge generator is not somehow poisoned. Even if the prover did not collude with the protocol designer to poison it directly, if she can infer any information about the internal state of the verifier from the instances he proposes, she may be able to solve future challenges much more easily than would be possible by random chance. [1]: https://arxiv.org/pdf/cs/0606037.pdf https://arxiv.org/pdf/cs/0606037.pdf