1
$\begingroup$

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?
$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks a lot! I was not sure, whether 0 was also in $Z_q$. Your explanations helped me a lot!! $\endgroup$ – Linus Sep 4 '19 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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