= Cryptographic witness
{title2=$w$}
A \b[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.<Probabilistic Proof Systems: A Primer by Oded Goldreich>[Section2.3, witness information and proofs of knowledge]{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. Both
$$
w_1=(1\mapsto1,\ 2\mapsto2,\ 3\mapsto3)
$$
and
$$
w_2=(1\mapsto3,\ 2\mapsto2,\ 3\mapsto1)
$$
are 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.
Back to article page
