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.

As the program of the prover does not necessarily spit out the knowledge itself (as is the case for zero-knowledge proofs[1]) 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.

the set of witnesses for x that should be accepted in the proof.

is a two party protocol with a prover

with the following two properties: This is a more rigorous definition of Validity:[2] Let

is used to express what is meant by the knowledge of a Turing machine.

it can be seen as being stronger than the soundness of ordinary 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.

in which solving the discrete logarithm problem is believed to be hard.

holds corresponds to solving the discrete logarithm problem.

One of the simplest and frequently used proofs of knowledge, the proof of knowledge of a discrete logarithm, is due to Schnorr.

[3] The protocol is defined for a cyclic group

We can see this is a valid proof of knowledge because it has an extractor that works as follows: Since

This protocol happens to be zero-knowledge, though that property is not required for a proof of knowledge.

Protocols which have the above three-move structure (commitment, challenge and response) are called sigma protocols.

[4] The naming originates from Sig, referring to the zig-zag symbolizing the three moves of the protocol, and MA, an abbreviation of "Merlin-Arthur".

[5] 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.

are equal or fulfill some other linear relation.

, we say that the prover proves knowledge of

Equality corresponds to the special case where a = 1 and b = 0.

this is equivalent to proving knowledge of an x such that

This is the intuition behind the following notation,[6] 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.

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.