Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
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. –  David Cash Mar 20 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. –  poncho Mar 20 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? –  DrLecter Mar 20 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 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 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?

share|improve this answer
    
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. –  poncho Mar 20 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. $\;$ –  Ricky Demer Mar 20 at 23:39
2  
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". –  poncho Mar 21 at 1:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.