Proof of knowledge
Class of interactive proof / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Proof of knowledge?
Summarize this article for a 10 year old
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[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.
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.