Proof of knowledge

<h2 id="details-on-the-definition">Details on the definition</h2>
This is a more rigorous definition of Validity:<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a>
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 {\tilde {P}}}
 
, such that for every 
 
 
 
 
 
 
 P
 ~
 
 
 
 
 
 {\displaystyle {\tilde {P}}}
 
, it is the case that 
 
 
 
 
 E
 
 
 
 
 P
 ~
 
 
 
 (
 x
 )
 
 
 (
 x
 )
 ∈
 W
 (
 x
 )
 ∪
 {
 ⊥
 }
 
 
 {\displaystyle E^{{\tilde {P}}(x)}(x)\in W(x)\cup \{\bot \}}
 
 and 
 
 
 
 Pr
 (
 
 E
 
 
 
 
 P
 ~
 
 
 
 (
 x
 )
 
 
 (
 x
 )
 ∈
 W
 (
 x
 )
 )
 ≥
 Pr
 (
 
 
 
 P
 ~
 
 
 
 (
 x
 )
 ↔
 V
 (
 x
 )
 →
 1
 )
 −
 κ
 (
 x
 )
 .
 
 
 {\displaystyle \Pr(E^{{\tilde {P}}(x)}(x)\in W(x))\geq \Pr({\tilde {P}}(x)\leftrightarrow V(x)\rightarrow 1)-\kappa (x).}

The result 
 
 
 
 ⊥
 
 
 {\displaystyle \bot }
 
 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 <a href="/facts/Turing_machine/ojCtglYu">Turing machine</a>. If 
 
 
 
 E
 
 
 {\displaystyle E}
 
 can extract 
 
 
 
 w
 
 
 {\displaystyle w}
 
 from 
 
 
 
 
 
 
 P
 ~
 
 
 
 
 
 {\displaystyle {\tilde {P}}}
 
, we say that 
 
 
 
 
 
 
 P
 ~
 
 
 
 
 
 {\displaystyle {\tilde {P}}}
 
 knows the value of 
 
 
 
 w
 
 
 {\displaystyle w}
 
.
This definition of the validity property is a combination of the validity and strong validity properties.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> 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 <a href="/facts/Soundness_(interactive_proof)/avws5tX1">soundness</a> of ordinary <a href="/facts/Interactive_proof_system/rDB0agR9">interactive proofs</a>.

<h2 id="relation-to-general-interactive-proofs">Relation to general interactive proofs</h2>
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 
 
 
 
 ⟨
 g
 ⟩
 
 
 {\displaystyle \langle g\rangle }
 
 be a <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a> with generator 
 
 
 
 g
 
 
 {\displaystyle g}
 
 in which solving the <a href="/facts/Discrete_logarithm/k8TXh5bL">discrete logarithm</a> problem is believed to be hard. Deciding membership of the language 
 
 
 
 L
 =
 {
 x
 ∣
 
 g
 
 w
 
 
 =
 x
 }
 
 
 {\displaystyle L=\{x\mid g^{w}=x\}}
 
 is trivial, as every 
 
 
 
 x
 
 
 {\displaystyle x}
 
 is in 
 
 
 
 ⟨
 g
 ⟩
 
 
 {\displaystyle \langle g\rangle }
 
. However, finding the witness 
 
 
 
 w
 
 
 {\displaystyle w}
 
 such that 
 
 
 
 
 g
 
 w
 
 
 =
 x
 
 
 {\displaystyle g^{w}=x}
 
 holds corresponds to solving the discrete logarithm problem.

<h2 id="protocols">Protocols</h2>
<h3>Schnorr protocol</h3>
One of the simplest and frequently used proofs of knowledge, the proof of knowledge of a <a href="/facts/Discrete_logarithm/k8TXh5bL">discrete logarithm</a>, is due to Schnorr.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> The protocol is defined for a <a href="/facts/Cyclic_group/JL5zfFuL">cyclic group</a> 
 
 
 
 
 G
 
 q
 
 
 
 
 {\displaystyle G_{q}}
 
 of order 
 
 
 
 q
 
 
 {\displaystyle q}
 
 with generator 
 
 
 
 g
 
 
 {\displaystyle g}
 
.
In order to prove knowledge of 
 
 
 
 x
 =
 
 log
 
 g
 
 
 ⁡
 y
 
 
 {\displaystyle x=\log _{g}y}
 
, the prover interacts with the verifier as follows:

<ol><li>In the first round the prover commits himself to randomness 
 
 
 
 r
 
 
 {\displaystyle r}
 
; therefore the first message 
 
 
 
 t
 =
 
 g
 
 r
 
 
 
 
 {\displaystyle t=g^{r}}
 
 is also called commitment.</li>
<li>The verifier replies with a challenge 
 
 
 
 c
 
 
 {\displaystyle c}
 
 chosen at random.</li>
<li>After receiving 
 
 
 
 c
 
 
 {\displaystyle c}
 
, the prover sends the third and last message (the response) 
 
 
 
 s
 =
 r
 +
 c
 x
 
 
 {\displaystyle s=r+cx}
 
 reduced modulo the order of the group.</li></ol>
The verifier accepts, if 
 
 
 
 
 g
 
 s
 
 
 =
 t
 
 y
 
 c
 
 
 
 
 {\displaystyle g^{s}=ty^{c}}
 
.
We can see this is a valid proof of knowledge because it has an extractor that works as follows:

<ol><li>Simulate the prover to output 
 
 
 
 t
 =
 
 g
 
 r
 
 
 
 
 {\displaystyle t=g^{r}}
 
. The prover is now in state 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
.</li>
<li>Generate random value 
 
 
 
 
 c
 
 1
 
 
 
 
 {\displaystyle c_{1}}
 
 and input it to the prover. It outputs 
 
 
 
 
 s
 
 1
 
 
 =
 r
 +
 
 c
 
 1
 
 
 x
 
 
 {\displaystyle s_{1}=r+c_{1}x}
 
.</li>
<li>Rewind the prover to state 
 
 
 
 Q
 
 
 {\displaystyle Q}
 
. Now generate a different random value 
 
 
 
 
 c
 
 2
 
 
 
 
 {\displaystyle c_{2}}
 
 and input it to the prover to get 
 
 
 
 
 s
 
 2
 
 
 =
 r
 +
 
 c
 
 2
 
 
 x
 
 
 {\displaystyle s_{2}=r+c_{2}x}
 
.</li>
<li>Output 
 
 
 
 (
 
 s
 
 1
 
 
 −
 
 s
 
 2
 
 
 )
 (
 
 c
 
 1
 
 
 −
 
 c
 
 2
 
 
 
 )
 
 −
 1
 
 
 
 
 {\displaystyle (s_{1}-s_{2})(c_{1}-c_{2})^{-1}}
 
.</li></ol>
Since 
 
 
 
 (
 
 s
 
 1
 
 
 −
 
 s
 
 2
 
 
 )
 =
 (
 r
 +
 
 c
 
 1
 
 
 x
 )
 −
 (
 r
 +
 
 c
 
 2
 
 
 x
 )
 =
 x
 (
 
 c
 
 1
 
 
 −
 
 c
 
 2
 
 
 )
 
 
 {\displaystyle (s_{1}-s_{2})=(r+c_{1}x)-(r+c_{2}x)=x(c_{1}-c_{2})}
 
, the output of the extractor is precisely 
 
 
 
 x
 
 
 {\displaystyle x}
 
.
This protocol happens to be <a href="/facts/Zero-knowledge_proof/38soaPT5">zero-knowledge</a>, though that property is not required for a proof of knowledge.

<h3>Sigma protocols</h3>
Protocols which have the above three-move structure (commitment, challenge and response) are called sigma protocols.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> 
The naming originates from Sig, referring to the zig-zag symbolizing the three moves of the protocol, and MA, an abbreviation of "Merlin-Arthur".<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> 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 
 
 
 
 
 y
 
 1
 
 
 
 
 {\displaystyle y_{1}}
 
 and 
 
 
 
 
 y
 
 2
 
 
 
 
 {\displaystyle y_{2}}
 
 with respect to bases 
 
 
 
 
 g
 
 1
 
 
 
 
 {\displaystyle g_{1}}
 
 and 
 
 
 
 
 g
 
 2
 
 
 
 
 {\displaystyle g_{2}}
 
 are equal or fulfill some other <a href="/facts/Linear/fChtg3KC">linear</a> <a href="/facts/Relation_(mathematics)/HjblDaMy">relation</a>. For a and b elements of 
 
 
 
 
 Z
 
 q
 
 
 
 
 {\displaystyle Z_{q}}
 
, we say that the prover proves knowledge of 
 
 
 
 
 x
 
 1
 
 
 
 
 {\displaystyle x_{1}}
 
 and 
 
 
 
 
 x
 
 2
 
 
 
 
 {\displaystyle x_{2}}
 
 such that 
 
 
 
 
 y
 
 1
 
 
 =
 
 g
 
 1
 
 
 
 x
 
 1
 
 
 
 
 ∧
 
 y
 
 2
 
 
 =
 
 g
 
 2
 
 
 
 x
 
 2
 
 
 
 
 
 
 {\displaystyle y_{1}=g_{1}^{x_{1}}\land y_{2}=g_{2}^{x_{2}}}
 
 and 
 
 
 
 
 x
 
 2
 
 
 =
 a
 
 x
 
 1
 
 
 +
 b
 
 
 {\displaystyle x_{2}=ax_{1}+b}
 
. Equality corresponds to the special case where a = 1 and b = 0. As 
 
 
 
 
 x
 
 2
 
 
 
 
 {\displaystyle x_{2}}
 
 can be <a href="/facts/Trivial_(mathematics)/AqzUxokN">trivially</a> computed from 
 
 
 
 
 x
 
 1
 
 
 
 
 {\displaystyle x_{1}}
 
 this is equivalent to proving knowledge of an x such that 
 
 
 
 
 y
 
 1
 
 
 =
 
 g
 
 1
 
 
 x
 
 
 ∧
 
 y
 
 2
 
 
 =
 
 
 (
 
 g
 
 2
 
 
 a
 
 
 )
 
 
 x
 
 
 
 g
 
 2
 
 
 b
 
 
 
 
 {\displaystyle y_{1}=g_{1}^{x}\land y_{2}={(g_{2}^{a})}^{x}g_{2}^{b}}
 
.
This is the intuition behind the following notation,<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> which is commonly used to express what exactly is proven by a proof of knowledge.

P
        K
        {
        (
        x
        )
        :
        
          y
          
            1
          
        
        =
        
          g
          
            1
          
          
            x
          
        
        ∧
        
          y
          
            2
          
        
        =
        
          
            (
            
              g
              
                2
              
              
                a
              
            
            )
          
          
            x
          
        
        
          g
          
            2
          
          
            b
          
        
        }
        ,
      
    
    {\displaystyle 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.

<h2 id="applications">Applications</h2>
Proofs of knowledge are useful tool for the construction of identification protocols, and in their non-interactive variant, signature schemes. Such schemes are:

<ul><li><a href="/facts/Schnorr_signature/YUqfT85P">Schnorr signature</a></li></ul>
They are also used in the construction of <a href="/facts/Group_signature/N1RtFwQM">group signature</a> and <a href="/facts/Digital_credential/3nyLl2px">anonymous digital credential</a> systems.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Cryptographic_protocol/0WuyTkFo">Cryptographic protocol</a></li>
<li><a href="/facts/Zero-knowledge_proof/38soaPT5">Zero-knowledge proof</a></li>
<li><a href="/facts/Interactive_proof_system/rDB0agR9">Interactive proof system</a></li>
<li><a href="/facts/Topics_in_cryptography/E6r9ID3G">Topics in cryptography</a></li>
<li><a href="/facts/Zero-knowledge_password_proof/vgebecKq">Zero-knowledge password proof</a></li>
<li><a href="/facts/Soundness_(interactive_proof)/avws5tX1">Soundness (interactive proof)</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The knowledge complexity of interactive proof-systems. Proceedings of 17th Symposium on the Theory of Computation, Providence, Rhode Island. 1985. Draft. Extended abstract <a href="/wiki/Shafi_Goldwasser" target="_blank">/wiki/Shafi_Goldwasser</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Mihir Bellare, Oded Goldreich: On Defining Proofs of Knowledge. CRYPTO 1992: 390–420 <a href="/wiki/Mihir_Bellare" target="_blank">/wiki/Mihir_Bellare</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Mihir Bellare, Oded Goldreich: On Defining Proofs of Knowledge. CRYPTO 1992: 390–420 <a href="/wiki/Mihir_Bellare" target="_blank">/wiki/Mihir_Bellare</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">C P Schnorr, Efficient identification and signatures for smart cards, in G Brassard, ed. Advances in Cryptology – Crypto '89, 239–252, Springer-Verlag, 1990. Lecture Notes in Computer Science, nr 435 <a href="/wiki/Claus_P._Schnorr" target="_blank">/wiki/Claus_P._Schnorr</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">[1] On Sigma protocols <a href="https://cs.au.dk/~ivan/Sigma.pdf" target="_blank">https://cs.au.dk/~ivan/Sigma.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">[2] Modular Design of Secure yet Practical Cryptographic Protocols <a href="https://ir.cwi.nl/pub/21438" target="_blank">https://ir.cwi.nl/pub/21438</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Proof Systems for General Statements about Discrete Logarithms <a href="https://crypto.ethz.ch/publications/files/CamSta97b.pdf" target="_blank">https://crypto.ethz.ch/publications/files/CamSta97b.pdf</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
</ol>

Proof of knowledge open-in-new

Proof of knowledge