# What is a “witness” in zero knowledge proof?

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?

• – user991 Feb 1 '17 at 10:24

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$.