= Zero-knowledge proof
A \b[zero-knowledge proof] is a proof protocol that convinces a verifier of a public statement's validity while revealing no additional information that the verifier could not efficiently obtain from that statement and its permitted prior information. The formal comparison uses a <zero-knowledge simulator>: an efficient <randomized algorithm> that reproduces the verifier's view without the prover's secret <cryptographic witness>.<Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems by Oded Goldreich and others>[Definition of zero knowledge, simulator and verifier-view distributions]{ref}
An <interactive proof system> separates three questions. <Completeness of an interactive proof> asks whether an honest prover can convince the verifier of a true statement. <Soundness of an interactive proof> bounds acceptance of false statements. Zero knowledge concerns information disclosure, so a protocol can pass a soundness test without being zero knowledge. The simulator comparison may require equality of distributions, statistical closeness or <computational indistinguishability>, depending on the definition.<Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems by Oded Goldreich and others>[Definitions of interactive proofs, zero knowledge and distribution comparison]{ref}
For an original soundness calculation, suppose a fixed false-statement strategy can answer only one of two equally likely challenges. Its acceptance probability is at most $1/2$. If this conditional bound continues to hold after every preceding transcript and fresh challenges are used, $k$ sequential successful rounds have probability at most
$$
\Pr(\text{all rounds accept})\leq\left(\frac12\right)^k.
$$
At $k=20$, the bound is $2^{-20}\approx9.54\times10^{-7}$. This stipulated calculation does not prove that any particular protocol has the required per-round bound, nor does it establish zero knowledge.
The simulator supplies the separate privacy argument. It must reproduce the relevant distribution efficiently, rather than merely output one accepting transcript. A <zero-knowledge proof> can be interactive or a <non-interactive zero-knowledge proof>; its precise verifier and setup assumptions are part of its security claim.
Back to article page
