Proof of knowledge

In cryptography, a proof of knowledge is an interactive proof in which the prover succeeds in 'convincing' a verifier that the prover knows something. What it means for a machine to 'know something' is defined in terms of computation. A machine 'knows something', if this something can be computed, given the machine as an input. As the program of the prover does not necessarily spit out the knowledge itself (as is the case for zero-knowledge proofs) a machine with a different program, called the knowledge extractor is introduced to capture this idea. We are mostly interested in what can be proven by polynomial time bounded machines. In this case the set of knowledge elements is limited to a set of witnesses of some language in NP.
Let formula_1 be a statement of language formula_2 in NP, and formula_3 the set of witnesses for x that should be accepted in the proof. This allows us to define the following relation: formula_4.
A proof of knowledge for relation formula_5 with knowledge error formula_6 is a two
party protocol with a prover formula_7 and a verifier formula_8 with the following two properties:
Details on the definition.
This is a more rigorous definition of Validity:
Let formula_5 be a witness relation, formula_3 the set of all witnesses for public value formula_1, and formula_6 the knowledge error.
A proof of knowledge is formula_6-valid if there exists a polynomial-time machine formula_15, given oracle access to formula_16, such that for every formula_16, it is the case that formula_26 and formula_27
The result formula_28 signifies that the Turing machine formula_15 did not come to a conclusion.
The knowledge error formula_30 denotes the probability that the verifier formula_8 might accept formula_1, even though the prover does in fact not know a witness formula_11. The knowledge extractor formula_15 is used to express what is meant by the knowledge of a Turing machine. If formula_15 can extract formula_11 from formula_16, we say that formula_16 knows the value of formula_11.
This definition of the validity property is a combination of the validity and strong validity properties in. For small knowledge errors formula_30, such as e.g. formula_41 or formula_42 it can be seen as being stronger than the soundness of ordinary interactive proofs.
Relation to general interactive proofs.
In order to define a specific proof of knowledge, one need not only define the language, but also the witnesses the verifier should know. In some cases proving membership in a language may be easy, while computing a specific witness may be hard. This is best explained using an example:
Let formula_43 be a cyclic group with generator formula_44 in which solving the discrete logarithm problem is believed to be hard. Deciding membership of the language formula_45 is trivial, as every formula_1 is in formula_43. However, finding the witness formula_11 such that formula_49 holds corresponds to solving the discrete logarithm problem.
Protocols.
Schnorr protocol.
One of the simplest and frequently used proofs of knowledge, the "proof of knowledge of a discrete logarithm", is due to Schnorr. The protocol is defined for a cyclic group formula_50 of order formula_51 with generator formula_44.
In order to prove knowledge of formula_53, the prover interacts with the verifier as follows:
The verifier accepts, if formula_59.
We can see this is a valid proof of knowledge because it has an extractor that works as follows:
Since formula_68, the output of the extractor is precisely formula_1.
This protocol happens to be zero-knowledge, though that property is not required for a proof of knowledge.
Sigma protocols.
Protocols which have the above three-move structure (commitment, challenge and response) are called "sigma protocols". The Greek letter formula_70 visualizes the flow of the protocol. Sigma protocols exist for proving various statements, such as those pertaining to discrete logarithms. Using these proofs, the prover can not only prove the knowledge of the discrete logarithm, but also that the discrete logarithm is of a specific form. For instance, it is possible to prove that two logarithms of formula_71 and formula_72 with respect to bases formula_73 and formula_74 are equal or fulfill some other linear relation. For "a" and "b" elements of formula_75, we say that the prover proves knowledge of formula_76 and formula_77 such that formula_78 and formula_79. Equality corresponds to the special case where "a" = 1 and "b" = 0. As formula_77 can be trivially computed from formula_76 this is equivalent to proving knowledge of an "x" such that formula_82.
This is the intuition behind the following notation, which is commonly used to express what exactly is proven by a proof of knowledge.
states that the prover knows an "x" that fulfills the relation above.
Applications.
Proofs of knowledge are useful tool for the construction of identification protocols, and in their non-interactive variant, signature schemes. Such schemes are:
They are also used in the construction of group signature and anonymous digital credential systems.