I'm trying to follow CCat's Zero Knowledge Proof example, which was quite similar to the $\Sigma$-protocol example in my books. And whith both of them I'm struggeling. When I try to test CCats Example:


Cyclic Group $G$ of size $p=17$. Generator $g=3$.


knows $x=7$
calculates $y=g^x=3^7\mod{17}=11$
generates $r=13$
sends $a=g^r=3^{13}\mod{17}=12$ to Bob


generates $c=15$ and sends it to Alice


sends $z=cx+r\mod{p}=(15\cdot 7+13)\mod{17}=16$ to Bob


checks if $g^z = y^c a$
$3^{16}\mod{17} = 11^{15} \cdot 12 \mod{17}$
$1=15$ (not good)

Without the Modulo, the comparison seams mathematical correct to me:

$g^{cx+r}=g^{x^c}\cdot g^r$

And the results are correct, in that case.

For some reasons $g^{cx+r\mod{p}}$ (or any variations) operation don't work for my examples. I also couldn't find any Congruence rules for a modulo within a power operation.

What am I missing?

  • 3
    $\begingroup$ Welcome to MO! This question does not appear to be a question related to current mathematical research and as such does not seem appropriate for this site. I believe what you are missing is that the multiplicative group generated by 3 modulo 17 is not a group of order 17. $\endgroup$
    – quid
    Jul 24 '13 at 14:09

Let me expand on the comment of @quid.

You should consider the ring $\mathbb{Z}_{17}$ of integers modulo $17$, which happens to be a field, as $17$ is prime. This is a cyclic group of order $17$ when regarded additively, whereas $\mathbb{Z}_{17}^{\star} = \mathbb{Z}_{17} \setminus \{ 0 \}$ is a cyclic group of order $16$ with respect to multiplication, of which your $g$ happens to be a generator.

Now you have $$ g^{u} = g^{v} \pmod{17} \qquad\text{if and only if}\qquad u \equiv v \pmod{16}. $$

So the correct calculation is $z = c x + r \equiv 16 \pmod{16}$. And then you have indeed $$ 15 \equiv g^{z} \equiv g^{c x + r} \equiv (g^{x})^{c} g^{r} \equiv y^{c} g^{r} \equiv 14 \cdot 12 \pmod{17}. $$

Note also that your $\LaTeX$ code

   g^{cx+r}=g^{x^c}\cdot g^r

which yields the possibly ambiguous $$g^{cx+r}=g^{x^c}\cdot g^r,$$ is a misprint for the correct

  g^{c x + r} = (g^{x})^{c} \cdot g^{r}

which yields $$g^{c x + r} = (g^{x})^{c} \cdot g^{r}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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