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.
Contents
- Details on the definition
- Relation to general interactive proofs
- Schnorr protocol
- Sigma protocols
- Applications
- References
Let
A proof of knowledge for relation
- Completeness: if
( x , w ) ∈ R , the prover P who knows witnessw forx succeeds in convincing the verifierV of his knowledge. More formally:Pr ( P ( x , w ) ↔ V ( x ) → 1 ) = 1 - Validity: Validity requires that the success probability of a knowledge extractor
E in extracting the witness, given oracle access to a possibly malicious proverP ~ P ~
Details on the definition
This is a more rigorous definition of Validity:
Let
The result
The knowledge error
This definition of the validity property is a combination of the validity and strong validity properties in. For small knowledge errors
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
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
In order to prove knowledge of
- In the first round the prover commits himself to randomness
r ; therefore the first messaget = g r - The verifier replies with a challenge
c chosen at random. - After receiving
c , the prover sends the third and last message (the response)s = r + c x .
The verifier accepts, if
Sigma protocols
Protocols which have the above three-move structure (commitment, challenge and response) are called sigma protocols. The Greek letter
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.