Questions regarding random values in Schnorr authentication

Question

In Chapter 21.3 of Schneier, Applied Cryptography I read the following about the Schnorr Authentication Protocol:

To generate a key pair, first choose two primes, $p$ and $q$, such that $q$ is a prime factor of $p - 1$. Then, choose an $a$ not equal to $1$, such that $a^q \equiv 1 \pmod{p}$. Then choose a random number less than $q$. This is the private key $s$. Then calculate $v = a^{-s} \mod p$. This is the public key.

Authentication Protocol

(1) Peggy picks a random number, $r$, less than $q$, and computes $x = a^r \mod p$.

(2) Peggy sends $x$ to Victor.

(3) Victor sends Peggy a random number, $e$, between $0$ and $2^t - 1$. (I’ll discuss $t$ in a moment.)

(4) Peggy computes $y = (r + se) \mod q$ and sends $y$ to Victor.

(5) Victor verifies that $x = a^yv^e \mod p$.

The security is based on the parameter $t$. The difficulty of breaking the algorithm is about $2t$. Schnorr recommended that $p$ be about $512$ bits, $q$ be about $140$ bits, and $t$ be $72$.

I have two questions regarding this:

1. Why can $r$ not also be $q$? This would make the commitment $x=1$, but what would be the problem with that?
2. Why is the challenge $t$ not allowed to be as large as $q$? It would not break anything, would it? I even found this lecture on Youtube where the lecturer lets the challenge (there denomiated $c$) be $c \in \mathbb{Z}_q$. Does limiting the size of $t$ make the procedure more efficient? If so, how?

Answer 1

Your first question: $r$ is taken from the group $Z_q$ ranging from 0 to $q-1$, and $q\equiv 0 \bmod q$, i.e. $q$ is the same as 0 in this group. Thus if you allow $q$ to be chosen, then $r$ is not uniform: you get 0 with a probability $2/(q+1)$ and all other elements in $Z_q$ with a probability $1/(q+1)$. Not really a big deal since the difference in probability is anyway negligible, but it is enough to annoy cryptographers.

Your second question: it really depends on what kind of zero-knowledge property you want. If you want zero-knowledge (without restriction), you have to have a small $t$; if you just want honest verifier zero-knowledge, then you can choose $c$ from $Z_q$. The reason is that when you use $c$ from $Z_q$, you will run into big trouble when trying to prove zero-knowledge because there is not a way to construct a simulator to handle such a big $c$. The usual simulating strategy is to let the simulator guess $c$ randomly until it is the one chosen by the verifier, which does not work when the probability of guessing correctly is negligible (if $t$ is small then the probability is high). But if the verifier is honest, you don't need to simulate it, so it is fine.