In
cryptography
Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or ''-logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adver ...
, 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
A machine is a physical system using Power (physics), power to apply Force, forces and control Motion, movement to perform an action. The term is commonly applied to artificial devices, such as those employing engines or motors, but also to na ...
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
In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...
) 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
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
bounded machines. In this case the set of knowledge elements is limited to a set of witnesses of some
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of met ...
in
NP.
Let
be a statement 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:
# Completeness: If
, then the prover
who knows witness
for
succeeds in convincing the verifier
of his knowledge. More formally:
, i.e. given the interaction between the prover P and the verifier V, the probability that the verifier is convinced is 1.
# 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:
Mihir Bellare
Mihir Bellare is a cryptographer and professor at the University of California San Diego. He has published several seminal papers in the field of cryptography (notably in the area of provable security), many of which were co-written with Phillip R ...
, Oded Goldreich
On Defining Proofs of Knowledge
CRYPTO 1992: 390–420
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
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algori ...
. 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.
For small knowledge errors
, such as e.g.
or
it can be seen as being stronger than the
soundness
In logic or, more precisely, deductive reasoning, an argument is sound if it is both valid in form and its premises are true. Soundness also has a related meaning in mathematical logic, wherein logical systems are sound if and only if every formu ...
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
be a
cyclic group
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
with generator
in which solving the
discrete logarithm problem is believed to be hard. 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.
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
In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
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 himself 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'')
reduced modulo the order of the group.
The verifier accepts, if
.
We can see this is a valid proof of knowledge because it has an extractor that works as follows:
# Simulate the prover to output
. The prover is now in state
.
# Generate random value
and input it to the prover. It outputs
.
# Rewind the prover to state
. Now generate a different random value
and input it to the prover to get
.
# Output
.
Since
, the output of the extractor is precisely
.
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
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
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
relation
Relation or relations may refer to:
General uses
*International relations, the study of interconnection of politics, economics, and law on a global level
*Interpersonal relationship, association or acquaintance between two or more people
*Public ...
. 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,
Proof Systems for General Statements about Discrete Logarithms
/ref> 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 signature
In cryptography, a Schnorr signature is a digital signature produced by the Schnorr signature algorithm that was described by Claus Schnorr. It is a digital signature scheme known for its simplicity, among the first whose security is based on the ...
They are also used in the construction of 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. For example, a group signature scheme could b ...
and anonymous digital credential systems.
See also
* Cryptographic protocol
A security protocol (cryptographic protocol or encryption protocol) is an abstract or concrete protocol that performs a security-related function and applies cryptographic methods, often as sequences of cryptographic primitives. A protocol describe ...
* Zero-knowledge proof
In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true while the prover avoids conveying any additional information a ...
* 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: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order t ...
* Topics in cryptography
The following outline is provided as an overview of and topical guide to cryptography:
Cryptography (or cryptology) – practice and study of hiding information. Modern cryptography intersects the disciplines of mathematics, computer scien ...
* Zero-knowledge password proof In cryptography, a zero-knowledge password proof (ZKPP) is a type of zero-knowledge proof that allows one party (the prover) to prove to another party (the verifier) that it knows a value of a password, without revealing anything other than the fact ...
* Soundness (interactive proof)
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a ''prover'' and a ''verifier''. The parties interact by exchanging messages in order t ...
References
Computational complexity theory
Cryptography