1
$\begingroup$

I have some trouble in understanding the definition of Schnorr's Identification protocol. The is the definition that I received:

Prover and verifier agree on a cyclic group $G$ of prime order $q$ generated by $g$.

  1. The prover sends $r=g^k$ for a random $k$

  2. The verifier sends $e \in_R Z_q$

  3. The prover sends $s=k+xe$

  4. The verifier now verifies if $r=g^sy^{-e}$

Now I don't understand why $r$ and $e$ have different formulas. As far as I understand, $r$ is an element of the cyclic group $G$, and $e$ also. What is the difference between:

$\in_RZ_q$

and

$g^k$ for a random $k$

mean?

$\endgroup$
2
  • $\begingroup$ To make sure I understand your question: $k$ and $e$ are chosen uniformly from $\mathbb{Z}_q$, and the protocol itself relies on the hardness of discrete log, which is why $r \equiv g^k$ gets involved. Are you asking if $k$ and $e$ are different somehow? $\endgroup$
    – user47922
    May 28, 2017 at 4:20
  • $\begingroup$ $e$ is not an element of $G$ but of $\mathbb{Z}_q$. $G = \{g^0, g^1, ..., g^{q-1}\}$, $\mathbb{Z}_q = \{0,1,..,q-1\}$ $\endgroup$
    – Linus
    Aug 25, 2019 at 1:12

1 Answer 1

2
$\begingroup$

The difference is the amount of information you have about the structure of the numbers.

Let $e\in_R\mathbb Z_q$. Then you know that the $e$ you have, is a random number from that set. You know no more and no less.

Let $r=g^k$ for some $k\in_R\mathbb Z_q$. Then you know that the $r$ is a random number from the group and you know its discrete logarithm to a pre-defined element. The fact that you randomly picked $k$ doesn't matter, you still know it and can use it in step 3. Even better you know that it is highly unlikely that somebody else will be able to infer $k$ from $r$ (because that is the discrete logarithm problem).

So you see: You know a lot more about $r$ than about $e$ because it was generated in this slightly different way.

$\endgroup$
2
  • $\begingroup$ Ah, exactly what I didn't understand. Thanks! One small question, what is the difference between $\in_R$ and just $\in$ in this definition? $\endgroup$ May 28, 2017 at 11:44
  • 1
    $\begingroup$ @AlfonsIngomar $\in$ means "any element in the set", which means it would be totally fine to pick "1" every time you want this to hold. $\in_R$ means "an element sampled uniformly at random from the set", ie it guarantees the element to be random and unpredictable. $\endgroup$
    – SEJPM
    May 28, 2017 at 12:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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