- Proof of knowledge
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 forzero-knowledge proofs [Shafi Goldwasser ,Silvio Micali , andCharles Rackoff . [*http://portal.acm.org/citation.cfm?id=63434 The knowledge complexity of interactive proof-systems*] . "Proceedings of 17th Symposium on the Theory of Computation", Providence, Rhode Island. 1985. Draft. [*http://theory.lcs.mit.edu/~cis/pubs/shafi/1985-stoc.pdf Extended abstract*]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$ be a language element of language $L$ in NP, and $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\; in\; L,\; w\; in\; W(x)\}$.

A proof of knowledge for relation $R$ with knowledge error $kappa$ is a twoparty protocol with a prover $P$ and a verifier $V$ with the following two properties:

#

**Completeness**: if $(x,w)\; in\; R$, the prover P who knows witness $w$ for $x$ succeeds in convincing the verifier $V$ of his knowledge. More formally: $Pr(P(x,w)leftrightarrow\; V(x)\; ightarrow\; 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 prover $ilde\; P$, must be at least as high as the success probability of the prover $ilde\; P$ 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 , Oded Goldreich: [*http://www-cse.ucsd.edu/~mihir/papers/pok.ps On Defining Proofs of Knowledge*] .CRYPTO 1992: 390-420*

**Validity**: There exists a polynomial-time machine $E$, given oracle access to $ilde\; P$, such that for every $ilde\; P$ and every $x\; in;dom;\; R$, it is the case that $E^\{\; ilde\; P(x)\}(x)\; in\; R(x)\; cup\; \{\; ot\; \}$ and $Pr(E^\{\; ilde\; P(x)\}(x)\; in\; R(x))\; geq\; Pr(\; ilde\; P(x)leftrightarrow\; V(x)\; ightarrow\; 1)\; -\; kappa(x).$$R(x)$ is the set of all witnesses for public value $x$, while the result $ot$ signifies that the Turing machine $E$ did not come to a conclusion.

The knowledge error $kappa(x)$ denotes the probability that the verifier $V$ might accept $x$, even though the prover does in fact not know a witness $w$. The knowledge extractor $E$ is used to express what is meant by the knowledge of a

Turing machine . If $E$ can extract $w$ from $ilde\; P$, we say that $ilde\; P$ knows the value of $w$.The validity property can be seen as being stronger than the

**soundness**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 $langle\; g\; angle$ be a

cyclic group with generator $g$ in which solving thediscrete logarithm problem is believed to be hard. The deciding membership of the language $L=\{x\; |\; g^w=x\; \}$ is trivial, as every $x$ is in $langle\; g\; angle$. However, finding the witness $w$ such that $g^w=x$ holds corresponds to solving the discrete logarithm problem.**Protocols****chnorr protocol**One of the simplest and frequently used proofs of knowledge, the "proof of knowledge of a

discrete logarithm ", is the Schnorr protocol introduced in. [*C P Schnorr, Efficient identification and signatures for smart cards, in G Brassard, ed. Advances in Cryptology --*] The protocol is defined for aCrypto '89, 239-252,Springer-Verlag , 1990. Lecture Notes in Computer Science, nr 435cyclic group $G\_q$ of order $q$ with generator $g$.In order to prove knowledge of $x=log\_g\; y$, the prover interacts with the verifier as follows:

# In the first round the prover commits herself to randomness $r$; therefore the first message $t=g^r$ is also called "commitment".

# 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+cx$.The verifier accepts, if $g^s\; =\; t\; y^\{c\}$.

**igma protocols**Protocols which have the above three move structure: commitment, challenge and response, are called sigma protocols. The Greek $Sigma$ visualizes the flow of the protocol. Sigma protocols exist for proving various statements about discrete logarithms. Using these proofs, the prover cannot only prove 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 $y\_1$ and $y\_2$ with respect to bases $g\_1$ and $g\_2$ are equal or fulfill some other

linear relation . For "a" and "b" elements of $Z\_q$, we say that the prover proves knowledge of $x\_1$ and $x\_2$ such that $y\_1=\; g\_1^\{x\_1\}\; land\; y\_2=g\_2^\{x\_2\}$ and $x\_2\; =\; a\; x\_1\; +\; b$. Equality corresponds to the special case where "a=1" and "b=0". As $x\_2$ can be trivally computed from $x\_1$ this is equivalent to proving knowledge of an "x" such that $y\_1=\; g\_1^\{x\}\; land\; y\_2=\{(g\_2^a)\}^\{x\}\; g\_2^b$.This is the intuition behind the following notation, which is commonly used to express what exactly is proven by a proof of knowledge.

$PK\{(x):\; y\_1=\; g\_1^\{x\}\; land\; y\_2=\{(g\_2^a)\}^\{x\}\; g\_2^b\; \},$

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 They are also used in the construction of

group signature and anonymous digital credential systems.**References****ee also***

Cryptographic protocol

*Zero-knowledge proof

*interactive proof system

*Topics in cryptography

*Zero-knowledge password proof **External references*** [

*http://research.cyber.ee/~lipmaa/crypto/link/zeroknowledge/pok.php Helger Lipmaa's cryptology pointers*]

*Wikimedia Foundation.
2010.*

### Look at other dictionaries:

**Proof**— • The establishment of a disputed or controverted matter by lawful means or arguments. Catholic Encyclopedia. Kevin Knight. 2006. Proof Proof … Catholic encyclopedia**Knowledge**— • Knowledge, being a primitive fact of consciousness, cannot, strictly speaking, be defined; but the direct and spontaneous consciousness of knowing may be made clearer by pointing out its essential and distinctive characteristics Catholic… … Catholic encyclopedia**Knowledge Science**— is the discipline of understanding the mechanics through which humans and software based machines know, learn, change, and adapt their own behaviors. Throughout recorded history, knowledge has been made explicit through symbols, text and graphics … Wikipedia**proof**— Synonyms and related words: Christophany, Ditto copy, Photostat, Satanophany, Xerox, Xerox copy, absolute indication, account, acid test, acquaintance, affirmation, airtight, ammunition, angelophany, announcement, appearance, argument, assay,… … Moby Thesaurus**Proof that π is irrational**— Although the mathematical constant known as pi; (pi) has been studied since ancient times, and so has the concept of irrational number, it was not until the 18th century that π was proved to be irrational.In the 20th century, proofs were found… … Wikipedia**knowledge**— Synonyms and related words: IQ, account, acquaintance, adeptness, advice, announcement, appreciation, apprehension, awareness, blue book, briefing, broadening the mind, bulletin, caliber, capacity, cognition, communication, communique,… … Moby Thesaurus**Zero-knowledge proof**— In cryptography, a zero knowledge proof or zero knowledge protocol is an interactive method for one party to prove to another that a (usually mathematical) statement is true, without revealing anything other than the veracity of the statement.A… … Wikipedia**Non-interactive zero-knowledge proof**— Non interactive zero knowledge proofs are a variant of zero knowledge proofs. Blum, Feldman, and Micali [1] showed that a common reference string shared between the prover and the verifier is enough to achieve computational zero knowledge without … Wikipedia**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… … Wikipedia**Spinoza: metaphysics and knowledge**— G.H.R.Parkinson The philosophical writings of Spinoza are notoriously obscure, and they have been interpreted in many ways. Some interpreters see Spinoza as (in the words of a contemporary)1 ‘the reformer of the new [sc. Cartesian] philosophy’.… … History of philosophy