Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

migrated from mathoverflow.net Jul 24 '13 at 15:01

This question came from our site for professional mathematicians.

3  
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. –  quid Jul 24 '13 at 14:09

1 Answer 1

up vote 0 down vote accepted

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

share|improve this answer
    
thanks. now it's clear. –  Horst Lemke Jul 25 '13 at 14:35

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.