Proof of knowledge
Encyclopedia
In cryptography
, a proof of knowledge is an interactive proof
in which the prover succeeds 'convincing' a verifier that it 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
be a language element of language 
in NP, and 
the set of witnesses for x that should be accepted in the proof. This allows us to define the following relation: 
.
A proof of knowledge for relation
with knowledge error 
is a two
party protocol with a prover
and a verifier 
with the following two properties:
Let
be a witness relation, 
the set of all witnesses for public value 
, and 
the knowledge error.
A proof of knowledge is
-valid if there exists a polynomial-time machine 
, given oracle access to 
, such that for every 
, it is the case that 
and 
The result
signifies that the Turing machine 
did not come to a conclusion.
The knowledge error
denotes the probability that the verifier 
might accept 
, even though the prover does in fact not know a witness 
. The knowledge extractor 
is used to express what is meant by the knowledge of a Turing machine
. If
can extract 
from 
, we say that 
knows the value of 
.
This definition of the validity property is a combination of the validity and strong validity properties in . For small knowledge errors
, such as e.g. 
or 
it can be seen as being stronger than the soundness
of ordinary interactive proofs
.
Let
be a cyclic group
with generator
in which solving the discrete logarithm
problem is believed to be hard. The deciding membership of the language
is trivial, as every 
is in 
. However, finding the witness 
such that 
holds corresponds to solving the discrete logarithm problem.
, is due to Schnorr. The protocol is defined for a cyclic group
of order 
with generator 
.
In order to prove knowledge of
, the prover interacts with the verifier as follows:
The verifier accepts, if
.
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 
and 
with respect to bases 
and 
are equal or fulfill some other linear
relation
. For a and b elements of
, we say that the prover proves knowledge of 
and 
such that 
and 
. Equality corresponds to the special case where a = 1 and b = 0. As 
can be trivially
computed from
this is equivalent to proving knowledge of an x such that 
.
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.
They are also used in the construction of group signature
and anonymous digital credential
systems.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, a proof of knowledge is an interactive proof
Interactive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
in which the prover succeeds 'convincing' a verifier that it knows something. What it means for a machine
Abstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory...
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
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
in NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
.
Let
be a language element of language in NP, and the set of witnesses for x that should be accepted in the proof. This allows us to define the following relation: .A proof of knowledge for relation
with knowledge error is a twoparty protocol with a prover
and a verifier with the following two properties:- Completeness: if
, the prover P who knows witness 
for 
succeeds in convincing the verifier 
of his knowledge. More formally: 
- Validity: Validity requires that the success probability of a knowledge extractor
in extracting the witness, given oracle access to a possibly malicious prover 
, must be at least as high as the success probability of the prover 
in convincing the verifier. This Property guarantees that no prover that doesn't know the witness can succeed in convincing the verifier.
Details on the definition
This is a more rigorous definition of Validity:Let
be a witness relation, the set of all witnesses for public value , and the knowledge error.A proof of knowledge is
-valid if there exists a polynomial-time machine , given oracle access to , such that for every , it is the case that and The result
signifies that the Turing machine did not come to a conclusion.The knowledge error
denotes the probability that the verifier might accept , even though the prover does in fact not know a witness . The knowledge extractor is used to express what is meant by the knowledge of a Turing machineTuring machine
A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside a...
. If
can extract from , we say that knows the value of .This definition of the validity property is a combination of the validity and strong validity properties in . For small knowledge errors
, such as e.g. or it can be seen as being stronger than the soundnessSoundness (Interactive proof)
Soundness is a property of interactive proof systems that requires that no prover can make the verifier accept for a wrong statement y \not\in L except with some small probability...
of ordinary interactive proofs
Interactive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
.
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
be a cyclic groupCyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
with generator
in which solving the discrete logarithmDiscrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
problem is believed to be hard. The deciding membership of the language
is trivial, as every is in . However, finding the witness such that holds corresponds to solving the discrete logarithm problem.Schnorr protocol
One of the simplest and frequently used proofs of knowledge, the proof of knowledge of a discrete logarithmDiscrete logarithm
In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. In particular, an ordinary logarithm loga is a solution of the equation ax = b over the real or complex numbers...
, is due to Schnorr. The protocol is defined for a cyclic group
Cyclic group
In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element g such that, when written multiplicatively, every element of the group is a power of g .-Definition:A group G is called cyclic if there exists an element g...
of order with generator .In order to prove knowledge of
, the prover interacts with the verifier as follows:- In the first round the prover commits herself to randomness
; therefore the first message 
is also called commitment. - The verifier replies with a challenge
chosen at random. - After receiving
, the prover sends the third and last message (the response) 
.
The verifier accepts, if
.Sigma protocols
Protocols which have the above three move structure: commitment, challenge and response, are called sigma protocols. The Greek 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 and with respect to bases and are equal or fulfill some other linearLinear
In mathematics, a linear map or function f is a function which satisfies the following two properties:* Additivity : f = f + f...
relation
Relation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
. For a and b elements of
, we say that the prover proves knowledge of and such that and . Equality corresponds to the special case where a = 1 and b = 0. As can be triviallyTrivial (mathematics)
In mathematics, the adjective trivial is frequently used for objects that have a very simple structure...
computed from
this is equivalent to proving knowledge of an x such that .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:- Schnorr signatureSchnorr signatureIn cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm. Its security is based on the intractability of certain discrete logarithm problems. It is considered the simplest digital signature scheme to be provably secure in a random oracle model . It is...
They are also used in the construction of group signature
Group signature
A Group signature scheme is a method for allowing a member of a group to anonymously sign a message on behalf of the group. The concept was first introduced by David Chaum and Eugene van Heyst in 1991...
and anonymous digital credential
Digital credential
Digital credentials are the digital equivalent of paper-based credentials. Just as a paper-based credential could be a passport, a Driver's license, a membership certificate or some kind of ticket to obtain some service, such as a cinema ticket or a public transport ticket, a digital credential is...
systems.
See also
- Cryptographic protocolCryptographic protocolA security protocol is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods.A protocol describes how the algorithms should be used...
- Zero-knowledge proofZero-knowledge proofIn cryptography, a zero-knowledge proof or zero-knowledge protocol is an interactive method for one party to prove to another that a statement is true, without revealing anything other than the veracity of the statement....
- interactive proof systemInteractive proof systemIn computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
- Topics in cryptography
- Zero-knowledge password proofZero-knowledge password proofIn cryptography, a zero-knowledge password proof is an interactive method for one party to prove to another party that it knows a value of a password, without revealing anything other than the fact that it knows that password to the verifier...
- Soundness (interactive proof)Soundness (Interactive proof)Soundness is a property of interactive proof systems that requires that no prover can make the verifier accept for a wrong statement y \not\in L except with some small probability...