Cyclic Groups: Modulo operations in exponents possible?

Question

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:

Setup:

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

Alice:

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

Bob:

generates $c=15$ and sends it to Alice

Alice:

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

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?

Answer 1

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