Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In a zero knowledge proof, a prover interactively proves to a verifier that an NP statement is true. If the language is an NP complete language and if the prover runs in poly time, the only way a prover could make such a proof is when it has a witness. So, when a prover provides a ZK proof for an NP complete statement, the prover is proving he has knowledge of a satisfying witness.
So, what is a Zero knowledge proof of knowledge? How is it different from Zero knowledge?
How do you define "having" or "knowing" the witness?
This question, which is much less intuitive than it may seem, is the core reason behind the difference between proofs of language membership and proofs of knowledge. Even though it seems intuitively true, there is no known general reduction from "I can prove that this word belongs to this language" to "I know a NP-witness for this statement". The latter is, in fact, a much stronger requirement - we are asking about a specific piece of information $w$ such that some fixed polynomial-time relation $R$ outputs 1 on $(x,w)$ (where $x$ is the statement). As far as we know, it might be that someone can "prove that $x$ is in the language", in the sense of being able to send the appropriate messages in an interactive and probabilistic proof, without knowing the static and deterministic proof (i.e., the witness). It also often occurs that the language is trivial (every word belongs to the language), yet it is defined by a specific relation such that it is non-trivial to know a witness for a given word, with respect to this relation.
Well, let me give you an example: fix some prime-order cyclic group $\mathbb{G}$ with generator $g$, and consider the language $L = \{x \in \mathbb{G} : \exists w, x = g^w\}$. Yes, this is a trivial language: since $\mathbb{G}$ is cyclic, every element of $\mathbb{G}$ belongs to $L$. This means that the following is a valid interactive proof of language membership: the prover sends nothing, the verifier checks that $x$ is an element of the group $\mathbb{G}$, and accepts if it holds. But now, consider the relation that I used to define this language: $R(x,w) = 1$ iff $g^w = x$. Clearly, knowing a witness $w$ with respect to this specific relation is much stronger than just being able to show language membership: in the first case, we must show that we know the discrete log of $x$ in base $g$, while in the latter, there is nothing to do.
Now, to answer my own initial question: in cryptography, we define knowledge by saying that a party knows some information if this information can be efficiently learned from this party. Formally, this is stated as follows: a proof is a proof of knowledge of a witness $w$ if there exists a probabilistic polynomial-time extractor which, given the code of the prover, is able to extract the witness $w$ from the prover. This property is crucial in many security analysis. Typically, we will want show that a cheating prover allows us to reach a contradiction to some security property, and the extractor will help us in deriving this contradiction.
