# Questions regarding random values in Schnorr authentication

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?

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.
• Thanks a lot! I was not sure, whether 0 was also in $Z_q$. Your explanations helped me a lot!! – Linus Sep 4 '19 at 21:04