Proving a Theorem in Zero-Knowledge
J. W. Pope · 2004
In 1986, Manuel Blum claimed in his paper ”How to Prove a Theo-rem So No One Else Can Claim It ” that he could apply zero-knowledge methods to proving theorems in any proof system. He sketched a proof of this result, but gave no details. We give a background of zero-knowledge proofs and examine their applicability to the propositional calculus. We then examine Blum’s claim, assuming the existence of a proof-verifying program which can be modeled with a finite state machine, and complete the proof. However, we also show that a zero-knowledge proof demon-strating knowledge of a proof is no easier than actually determining a proof of a theorem from scratch. 1