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

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.

• Zero-knowledge proofs are usually interactive. It can be easier to use proof of knowledge in non interactive setting. – user4982 Sep 27 '13 at 18:51

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.

• Thanks for your answer, @K.G, but do you know of any example, context or situation in which proofs of knowledge are used, without being zero-knowledge proofs? Because it seems to me that whenever one wants to prove something, it's better to always do it in a zero-knowledge way. Is it right, or there are actually cases in which we might prefer proofs of knowledge and not zero-knowledge proofs? – LRM Sep 30 '13 at 13:44
• There's witness-indistinguishable proofs. But you are right, usually you want some variant of zero knowledge, since if you don't care about keeping the private input secret, you can just reveal the input. Still, the notions of zero knowledge and proof of knowledge are two different notions. – K.G. Sep 30 '13 at 13:49
• Proofs of knowledge are used for example to prove the knowledge of a trapdoor. If you consider discrete logarithms for an element $y$ to some base $x$, you want to prove that you know $\log_x y$. But obviously, you would also want your proof to be zero-knowledge in this case, or you could just state the solution and say "This is it, this is proof that I knew the solution". – tylo Nov 25 '14 at 15:08


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

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.