Re:Understanding Zero-knowledge proofs through illustrated e...
by tromp on Friday December 03, 2021 @02:51AM
(#29427663)
In many applications of zero knowledge proofs, you prove knowledge of solution to a puzzle that need not have a solution. E.g. graph isomorphism, a 3-coloring, a Sudoko puzzle. So the probability of guessing the solution can be 0, while there's a nonzero probability of convincing a verifier.
Even if you remove all the statistical nature from the system: They're trying to prove they have a piece of knowledge of finite size. If astronomical luck is a real concern, then you have to worry that even a non-probabilistic prover could have just guessed the knowledge.
Or as an analogy, even if you had a perfect and magically irreversible hash, someone could still guess the password first try.