Suppose one day I came up with a proof that 0 = 1 in some formal system such as PA or ZFC that cannot prove its own consistency (unless it is inconsistent). Would it be possible to have a zero-knowledge proof of this? In other words, would it be possible for me to convince you with high probability that I had derived such a proof without (feasibly) revealing the proof of the contradiction? (I haven't by the way…found such a contradiction.)
[Math] Zero-knowledge proof that 0 = 1
computational complexitylo.logicproof-theory
Best Answer
In this setting, the adversary seeks to find a deduction $\phi_0, \dots, \phi_n$ of $P \wedge \neg P$ quickly. If ZFC, for example, is inconsistent, there exists such a deduction and hence there exists a (constant time) adversary, which simply publishes $\phi$.
In order to have a zero-knowledge proof problem, one needs a family of problems, for which the adversary's task becomes increasingly hard as $n \rightarrow \infty$. With just one theory, such as ZFC, this does not happen.