2
$\begingroup$

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?

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Really Nice Answer. So, a verifier should not be able to learn anything more than whether the statement is in the language. Whereas, an extractor should be able to extract the witness from the prover. Why can't a cheating verifier play the role of an extractor and extract the witness? That would break Zero Knowledge property. $\endgroup$ – satya Apr 15 at 20:43
  • 1
    $\begingroup$ Great question! That's because the extractor is given an additional power that a honest verifier does not have: he has access to the code of the prover (for example, he can rewind it, change its random tape, etc). A normal verifier is only interacting with the prover, and has no such power. The distinction between the power of the verifier and that of the simulator is precisely what allows being zero-knowledge and being a proof of knowledge to be compatible - in a sense, that's the core subtlety of this concept. $\endgroup$ – Geoffroy Couteau Apr 15 at 20:46

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.