What is a “witness” in zero knowledge proof?

Question

I've seen the term "witness" tossed around when talking about knowledge extractors, but I have no idea what it means. I can't find a definition.

What is a “witness” in zero knowledge proof?

Answer 1

A witness for an NP statement is a piece of information that allows you to efficiently verify that the statement is true. For example, if the statement is that there exists a Hamiltonian cycle in some graph, a witness would be such cycle. Given a cycle, one can efficiently check whether it is a valid Hamiltonian cycle, but finding such cycle is difficult.

Knowledge extractors are used in the definition of proofs of knowledge. There, you don't just prove that some statement is true, but that you know a witness for this statement. A machine knowing something is defined via the existence of a knowledge extractor that, roughly speaking, interacts with the machine and then output the (extracted) witness.

Answer 2

Informally, suppose you have some subset of some bigger set. In general, it can be easy to define the subset mathematically, but in practice, it may be difficult to say if an element of the bigger set is in the subset or not. A witness for an element of the subset is something that allows you to easily verify that the element really is in the subset.

One example may be the following. Let $n$ be an RSA modulus. Some of the numbers from $1$ to $n-1$ are squares in the sense that they are congruent to the square of some integer modulo $n$. However, it seems to be hard to decide if a number is a square or not. (The Jacobi symbol allows you to identity some non-squares, but not all.)

But if you have a square $x$, a witness for that square is any integer $w$ such that $x \equiv w^2 \pmod{n}$, because you can easily check that this equation holds.

Of course, sometimes, determining membership is easy, but we still care about witnesses, but now only "useful" witnesses. For example, suppose $G$ is a cyclic group with generator $g$. Often, it is easy to check if something is a member of the group (but not always!), so a group element could be its own witness, so to speak. However, a more useful witness for an element $x$ being in the group could be an integer $w$ such that $x = g^w$, the discrete logarithm of $x$.