Soundness idea of basic zero knowledge prood I am having a hard time figuring out the soundness proof of the bellow zero knowledge protocol.  As it is a typical proof, I would love to deeply understand it.



zero knowledge argument that $h \in &lt;g&gt;$

Lets $G = (\mathbb{Z}/n\mathbb{Z})^{\times}$.  The prover wants to show to the verifier that $h \in &lt;g&gt;$.  The common inputs are $G, h, g$ and the prover has the value $a$ such that $h = g^{a}$.

The protocol goes like...

         Prover                         Verifier
--------------------------------------------------
y = g'^k mod n           y
                 ---------------&gt;  choose challenge c
                         c
                 &lt;---------------
s = k + c*r mod |G|
                         s
                 ---------------&gt;  check if g^s mod n = y*h^c mod n


In the case the protocol was poorly explained her, here is another version of it Non-interactive proof that an element is in a subgroup



Many thanks!

didier
There are a couple of problems with this zero knowledge proof;


it isn't explained very well
it gives the verifier more information than it claims to


Lets go through them in order:


  It isn't explained very well


The problem is that the terminology it uses in the proof statement differs from the terminology they use in the protocol description; for example, the protocol uses this value 'r' without explaining what that value is.  Here's the protocol redone to use the same terminology:

         Prover                         Verifier
--------------------------------------------------
Prover selects random value k
y = g^k mod n            y
                 ---------------&gt; 
                                   Verifier chooses challenge bit c
                         c
                 &lt;---------------
s = k + c*a mod n-1
                         s
                 ---------------&gt;  check if g^s mod n = y*h^c mod n


The idea is that, if the protocol is run honestly and if $h = g^a$, then the check will always verify, because $g^s = g^{k + ca} = g^k \cdot g^{ac} = y \cdot h^c$.  The further idea is that someone could try to create a valid looking transcript by selecting s and c first, and then computing $y = g^s (h^c)^{-1}$, with the hope that these randomly selected values would be indistinguishable from a valid set.


  It gives the verifier more information than it claims to


It claims to just show that $h \in &lt;g&gt;$, or in other words, there exists an $a$ such that $h = g^a$.  However, the verifier can deduce more than that; not only can he deduce that such an $a$ exists; but in addition that the prover knows that value.  In fact, this Zero Knowledge Proof is actually a proof-of-knowledge of the value of $a$, not just its existence.

You can show that we cannot really create the 'Zero Knowledge Proof' of a nontrival binary statement (one which is either true or false, but nontrivial in the sense that it cannot be deduced directly).  The reason is that the existence of such a ZKP protocol would allow someone to deduce the statement directly (without a prover being involved).  Consider if we had such a ZPF protocol, then someone could just assume that binary statement, and run the proof/verification mechanism honestly with themselves; if the proof verifies, then they have learned that the statement must be true.