ZKP Properties

Cryptography · Axiom Academy

Understanding the three essential properties that define zero-knowledge proofs: Completeness, Soundness, and Zero-Knowledge Completeness ensures that if the statement is true and both parties follow the protocol honestly, the verifier will always accept the proof. For all statements x in the language L and for all witnesses w, if (x, w) is valid: This means an honest prover with valid knowledge can always convince an honest verifier. Soundness ensures that if the statement is false, no cheating prover can convince the verifier to accept, except with negligible probability. For all statements x not in the language L and for all (possibly malicious) provers P*: where negl(n) is a negligible function - it decreases faster than any polynomial inverse. A stronger variant called proof of knowledge requires that if the verifier accepts, then there exists an efficient extractor that can extract the witness: Given access to the prover's internal state The extractor can compute the witness w This proves the prover actually "knows" the secret Zero-Knowledge ensures that the verifier learns nothing beyond the validity of the statement. The interaction reveals no information about the witness. Formal Definition (Simulatability) For every verifier V*, there exists a probabilistic polynomial-time simulator S such that for all x in L: where View(P,V*) is the verifier's view during the real interaction, and S(x) is the simulator's output.

This is the written version of the interactive lesson above. See the full Cryptography course.