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. 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. 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. Let x {displaystyle x} be a statement of language L {displaystyle L} in NP, and W ( x ) {displaystyle W(x)} the set of witnesses for x that should be accepted in the proof. This allows us to define the following relation: R = { ( x , w ) : x ∈ L , w ∈ W ( x ) } {displaystyle R={(x,w):xin L,win W(x)}} . A proof of knowledge for relation R {displaystyle R} with knowledge error κ {displaystyle kappa } is a twoparty protocol with a prover P {displaystyle P} and a verifier V {displaystyle V} with the following two properties: This is a more rigorous definition of Validity: Let R {displaystyle R} be a witness relation, W ( x ) {displaystyle W(x)} the set of all witnesses for public value x {displaystyle x} , and κ {displaystyle kappa } the knowledge error.A proof of knowledge is κ {displaystyle kappa } -valid if there exists a polynomial-time machine E {displaystyle E} , given oracle access to P ~ {displaystyle { ilde {P}}} , such that for every P ~ {displaystyle { ilde {P}}} , it is the case that E P ~ ( x ) ( x ) ∈ W ( x ) ∪ { ⊥ } {displaystyle E^{{ ilde {P}}(x)}(x)in W(x)cup {ot }} and Pr ( E P ~ ( x ) ( x ) ∈ W ( x ) ) ≥ Pr ( P ~ ( x ) ↔ V ( x ) → 1 ) − κ ( x ) . {displaystyle Pr(E^{{ ilde {P}}(x)}(x)in W(x))geq Pr({ ilde {P}}(x)leftrightarrow V(x) ightarrow 1)-kappa (x).} The result ⊥ {displaystyle ot } signifies that the Turing machine E {displaystyle E} did not come to a conclusion. The knowledge error κ ( x ) {displaystyle kappa (x)} denotes the probability that the verifier V {displaystyle V} might accept x {displaystyle x} , even though the prover does in fact not know a witness w {displaystyle w} . The knowledge extractor E {displaystyle E} is used to express what is meant by the knowledge of a Turing machine. If E {displaystyle E} can extract w {displaystyle w} from P ~ {displaystyle { ilde {P}}} , we say that P ~ {displaystyle { ilde {P}}} knows the value of w {displaystyle w} . This definition of the validity property is a combination of the validity and strong validity properties in. For small knowledge errors κ ( x ) {displaystyle kappa (x)} , such as e.g. 2 − 80 {displaystyle 2^{-80}} or 1 / p o l y ( | x | ) {displaystyle 1/mathrm {poly} (|x|)} it can be seen as being stronger than the soundness of ordinary interactive proofs.