Understanding the definition of Schnorrs identification protocol

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?

• 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? – user47922 May 28 '17 at 4:20
• $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\}$ – Linus Aug 25 '19 at 1:12

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.
• Ah, exactly what I didn't understand. Thanks! One small question, what is the difference between $\in_R$ and just $\in$ in this definition? – rzdzc2WUQKJeB6GS May 28 '17 at 11:44
• @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. – SEJPM May 28 '17 at 12:10