When would one prefer a proof of knowledge instead of a zero-knowledge proof?

Question

I've just realized I find it hard to distinguish between these two terms (proof of knowledge, and zero-knowledge proof), specially where only the latter seems to be used in many cryptographic protocols.

Zero-knowledge proofs are usually defined as those methods by which the prover manages to prove to the verifier that a given statement is true, without revealing any additional information apart from the fact that the statement is true. For example, let's say I want to prove knowledge of the plaintext of some ciphertext I've generated, so that everyone can check that the plaintext is of a certain form (a value within a certain range, for instance). It seems clear to me that in this case I'd be interested in using a zero-knowledge proof, because I don't want anyone else learning what my plaintext was, or which random value I used to encrypt it (I'm assuming I used a public key encryption scheme).

On the other hand, proofs of knowledge seem to be just defined as those proofs in which the prover convinces a verifier that he/she knows something (without stating any constraint about what the verifier can or cannot learn from his interaction with the prover). From the definitions, these two terms seem to be pretty different. However, I find it hard to see in which context one would be interested in using just proofs of knowledge, instead of zero-knowledge proofs.

Answer 1

Formally, this is all very complicated, but informally:

An interactive proof is a conversation between a prover and a verifier that ends with the verifier either accepting or rejecting.

The interactive proof can be zero knowledge, in which case a cheating verifier does not learn anything new by talking to the honest prover.

The interactive proof can be a proof of knowledge, where a cheating prover cannot convince an honest verifier to accept unless he (essentially) knows some secret.

The interactive proof can of course be both zero knowledge and a proof of knowledge.

Answer 2

$ \newcommand{\NP}{\mathbf{NP}} \newcommand{\coNP}{\mathbf{coNP}} \newcommand{\TFNP}{\mathbf{TFNP}} \newcommand{\L}{L} \newcommand{\R}{\mathcal{R}} $

A zero-knowledge proof of knowledge is useful in scenarios where the notion of a plain zero-knowledge proof is vacuous. I think the accepted answer kind of misses this (crucial) point.

For instance consider a hard language $\L$ in $\NP\cap\coNP$. That is, $\L\in\NP$ and $\L\in\coNP$, or equivalently $\L,\bar{\L}\in\NP$. By definition, there are two (efficiently-verifiable) $\NP$ relations $\R_0$ and $\R_1$ corresponding to $\L\in\NP$ and $\bar{\L}\in\NP$, respectively. Next, consider the "combined" $\NP$ relation $$\R=\R_1\cup\R_2:=\{(x,0w):(x,w)\in\R_0\}\cup\{(x,1w):(x,w)\in\R_1\}.$$ Note that the decision problem corresponding to $\R$ is trivial since every string $x$ has a either a $0$-witness or a $1$-witness. This also means that a zero-knowledge proof is vacuous for $\R$ since every $x$ is syntactically guaranteed a witness -- there is nothing for the verifier to learn about the existence of a witness. This is unlike, for instance, $SAT$ where a string $x$ could or could not have a witness.$^1$ The existence of a witness (i.e., a satisfying statement) in this case is something non-trivial a verifier can learn, and therefore it is meaningful to talk about learning this fact in zero-knowledge.$^2$ On the other hand, a proof of knowledge for $\R$ accomplishes something non-trivial since it convinces the verifier that the prover actually knows a witness (via the extractor).

It turns out that decision problems corresponding to some of the (computational) hard problems in cryptography are of the above form and therefore trivial. These precisely correspond to search problems that lie in $\TFNP$, the class of all total $\NP$ search problems (the search counterpart of $\NP\cap\coNP$). One such example is the discrete-logarithm problem in a (cyclic) group $G$ of prime order $p$. Given a generator $g$ and an element $h\in G$ we know there exists $a\in\mathbb{Z}_p$ such that $g^a=h$. Therefore zero-knowledgeness is trivial. But a prover can convince a verifer of the knowledge of the discrete-logarithm by using the Schnorr protocol. Interestingly, as pointed out in this thread, most interesting zero-knowledge proofs we know also turn out to be proofs of knowledge.

$^1$ This is one of the reasons $SAT$ is very hard. It is a needle in a haystack problem where we don't even know whether there exists a needle in the haystack.

$^2$ This witness is still hard to find though. Therefore there is something non-trivial to learn unlike in the case of languages in $\mathbf{P}$.

Answer 3

An interactive proof system, including one with zero knowledge property (a zero-knowledge proof) is to recognize a language. That is, to decide whether an input belongs to a subset or the whole set (universe). Proof of knowledge is an interactive system with a knowledge extractor algorithm.

Now consider Pedersen commitments, where any group element could be a valid commitment. This means "is a commitment" language is the universe itself. A $\Sigma$-type protocol for this commitment scheme has knowledge extractor with knowledge error inverse of group order.

It follows, proof of knowledge is the reasonable tool for proving statements about data committed with Pedersen commitment scheme, but not interactive proof system.

Answer 4

I find this question ten years later...

I'm reading On Defining PoK. In the appendix E, the author gives the ZKP of graph non-isomorphism, which invoke a subroutine for proving that $V$ gives a right $H$ to $P$.

This subroutine is WI proof of knowledge but not ZK, since it is a parallel composition.

And I think the reason for using this is that when we construct the simulator, we need to extract the $\pi~(s.t.~ \pi(G_{0/1})=H)$. So we need it to be PoK. But we don't need the ZK property for this subroutine.