 Cryptographic witness

A cryptographic witness is auxiliary information $w$ that satisfies an efficiently checkable relation for a public statement $x$. Writing the relation as $R(x,w)=1$ separates the claim from the information that certifies it. In a zero-knowledge proof, a prover may use such a witness without revealing it.^[ref]

For an original graph isomorphism example, let the public graphs $G$ and $H$ both be the path with edges $\{1,2\},\{2,3\}$. A witness is a bijection of vertices preserving adjacency. Bothandare valid. A witness need not be unique. With an adjacency-matrix encoding, a verifier can check all vertex pairs and their images in $O(n^2)$ comparisons for an $n$-vertex pair.

The public assertion is that a suitable mapping exists; the witness supplies one particular mapping. Whether that mapping is secret depends on the application. Calling it a witness does not inherently make it a password or a secret key.

A further distinction concerns what a proof establishes. Soundness of an interactive proof protects against acceptance of false statements. A proof of knowledge requires an additional formal relationship between a successful prover and extraction of a witness. Validity of a statement and knowledge of its certificate are not interchangeable claims.