Soundness idea of basic zero knowledge prood

Question

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 <g>$

Lets $G = (\mathbb{Z}/n\mathbb{Z})^{\times}$. The prover wants to show to the verifier that $h \in <g>$. 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
                 --------------->  choose challenge c
                         c
                 <---------------
s = k + c*r mod |G|
                         s
                 --------------->  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

Answer 1

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
                 ---------------> 
                                   Verifier chooses challenge bit c
                         c
                 <---------------
s = k + c*a mod n-1
                         s
                 --------------->  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 <g>$, 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.

Answer 2

Soundness does not necessarily hold.
If 2 < m and n = (m*m)-1 and h = (m*m)-2 and g = m, then h is not in the subgroup generated by g but y=1 and s=0 will cause any even challenge to result in acceptance.
What is the challenge space?