# 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 <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

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

• it isn't explained very well

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 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.

• Are you saying that a ZKPoK is inherently weaker because it leaks the fact that the prover knows the witness? Formally speaking, ZKPoK is stronger than plain ZKP. Mar 20, 2014 at 16:57
• @DavidCash: no, I am saying that there are statements for which no ZKPoK exists, and one such statement is $\exists x: g^x = h$ (at least, we don't think so; if either the DLP and factorization problem is easier than we think, the above statement may be trivial). There does exist a ZKPoK proof that "I know such a value $x$", however that's not the statement that was originally claimed. Mar 20, 2014 at 18:05
• @poncho You are talking about plain ZK in your last paragraph right? The verifier is computationally bounded (PPT). What about a verifier just given a graph and without the prover needs to deduce if it is for instance 3-colorable? How should the verifier run a meaningful proof/verification mechanism without having access to the prover who knows the witness and learn if the statement is true? Mar 20, 2014 at 18:11
• You should replace $n-1$ in your calculation of $s$ by the order of the subgroup. $g$ does not necessarily generate the full multiplicative subgroup. And y should be chosen smaller than the order of the subgroup.
– tylo
Mar 21, 2014 at 12:46
• concerning the difference between pure ZK proofs and proofs of knowledge, this is a proof of knowledge. Right now I can't think of a ZK proof of being in the according subgroup without knowing the element, but it might be possible.
– tylo
Mar 21, 2014 at 12:48

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?

• Zero knowledge proofs do not insist that a challenge be accepted only if the proposition being proved is true; in fact, they require that someone be able to generate a valid-looking transcript even if the proposition was false. Mar 20, 2014 at 15:43
• However, zero knowledge proofs by default do insist that the verifier has at most a $\hspace{1.14 in}$ negligible probability of accepting a false statement. $\;$
– user991
Mar 20, 2014 at 23:39
• Most ZKP's I've seen allow a 0.5 probability per round of accepting a false statement; that is consistent with your "any even challenge to result in acceptance". Mar 21, 2014 at 1:52