1
$\begingroup$

It has always been a question surrounding in my mind whether a zero-knowledge proof ($\mathrm{ZKP}$) is the same as zero-knowledge proof of knowledge ($\mathrm{ZKPoK}$), but it was not since today that these concepts are creating problems in my understanding of cryptography.

So, what is the real difference (if there is one) between $\mathrm{ZKP}$ and a $\mathrm{ZKPoK}$? Is people using both concepts indistinguishable?

Here is an answer difference that answers my question partially, but I am lookin forward a direct answer to mine.

$\endgroup$
2
$\begingroup$

Since you reference my answer to a very similar question, I'm assuming you already read it, so you know what the difference between ZK and ZKPoK is at a technical level. To recall briefly, though: a standard ZK proves the existence of a witness, while ZKPoK proves that the prover actually knows the witness, which is formalized by saying that there exists an efficient extractor which can recover the witness from the code of the prover. Actually, a better full name for "zero-knowledge proof" would be "zero-knowledge proof of membership" (it proves that a word $x$ belongs to a language $L$, which is equivalent to saying that there exists a witness for the statement "$x$ belongs to $L$").

To answer your main question:

So, what is the real difference (if there is one) between ZKP and a ZKPoK? Is people using both concepts indistinguishable?

There is a clear difference at the technical level, and this translates into a clear difference in the applications. First, zero-knowledge proofs are used as components in larger constructions of cryptographic objects (there are hundreds of example, but just to name a few: verifiable encryption, maliciously secure computation, anonymous credentials, etc). In many of those applications of ZK proofs, the proof of knowledge property is actually crucial. This is for example the case in verifiable encryption and anonymous credentials - but not in maliciously secure computation, where standard zero-knowledge suffice.

To give you an intuition of when the difference matters, here is a rule of thumb:

  • If you just want to prove that "some property is verified" (for example: "the ciphertext you sent me contains a bit"), zero-knowledge proofs (of membership) suffice.
  • If you need to authenticate the prover in any way, then you need a zero-knowledge proof of knowledge.

To put it even more directly: a ZK proofs only says something about the statement ("the statement is true"). A ZK proof of knowledge is much stronger since it also says something about the prover himself: "the statement is true, and the prover knows a witness for it". This is absolutely crucial in any "authenticated" cryptographic protocol: you can say that an authorized user (for whatever definition of "authorized" in your application) is a user that knows a witness; then, sending a ZKPoK can be seen as authenticating the user, without revealing is authentication credential (which prevents stealing his identity).

| improve this answer | |
$\endgroup$
  • $\begingroup$ So, in a ZKPoK the common properties Completeness, Soundness and Zero-Knowledge are satisfies, while in a ZK only Completeness and Zero-Knowledge. Am I right? $\endgroup$ – Bean Guy Sep 24 at 18:55
  • 1
    $\begingroup$ No, in a "standard" ZK proof, you have Completeness, Zero-Knowledge, and Soundness (= no cheating prover can find an accepting proof of a wrong statement). In a ZKPoK, you have Completeness, Zero-Knowledge, and Knowledge Extractibility (= for any prover which provides an accepting proof, there is an efficient extractor which can recover the secret witness from the code of the prover - which implies in particular that this witness exists, hence that the statement is true), which is a strictly stronger notion than soundness. $\endgroup$ – Geoffroy Couteau Sep 24 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.