# Domain parameters in the Schnorr identification scheme

I have been recently studying the Schnorr identification scheme. The book Cryptography: Theory and Practice by Stinson and Paterson states the following about the domain parameters in the Schnorr identification scheme:

The scheme requires a trusted authority, or TA, who chooses some common system parameters (domain parameters) for the scheme, as follows:

1. $$p$$ is a large prime (i.e., $$p\approx 2^{2048}$$).

2. $$q$$ is a large prime divisor of $$p-1$$ (i.e., $$q\approx 2^{224}$$).

3. $$\alpha \in \mathbb{Z}_p^*$$ has order $$q$$

4. $$t$$ is a security parameter such that $$q>2^t$$. (A security parameter is a parameter whose value can be chosen in order to provide a desired level of security in a given scheme. Here, the adversary's probability of deceiving Alice or Bob is $$2^{-t}$$, so $$t=80$$ will provide adequate security for most practical applications.)

My question is, how can we find such $$p$$, $$q$$, $$\alpha$$ and $$t$$? And why does it have to be $$p\approx 2^{2048}$$, $$q\approx 2^{224}$$ and $$t=80$$?

We will need an efficient primality test to produce $$p$$ and $$q$$. If you're happy with probable primes then the Miller-Rabin test will suffice for most practical purposes. Write IsPrime() for the test.

Firstly choose $$t$$ according to the security requirements of your scheme. There's a chance of $$2^{-t}$$ that a deceiver can subvert the scheme at random, so a choosing $$t=80$$ means that even if your attacker tried to spoof your system at random $$2^{80}$$ times they would on average only succeed once. Allowing an adversary $$2^{80}$$ attempts to spoof your system is unlikely to be a realistic proposition, so $$t=80$$ is considered fine in this regard.

We now find $$q$$, it should be large enough that an adversary cannot solve discrete logarithms in an arbitrary group of $$q$$ elements (e.g. using the baby-step-giant-step method) and also larger that $$2^t$$. If $$q\approx 2^{224}$$ then approximately $$2^{112}$$ group operations would be required by the method and so at least $$2^{112}$$ computational operations would be needed for BS-GS. To find 224-bit $$q$$ generate a random 223-bit number $$n$$ and let $$q_0=2^{223}+n$$. Compute IsPrime($$q_0$$) and if successful let $$q=q_0$$ otherwise increment $$q_0$$ by 1 and repeat until we are successful.

We now find $$p$$, it should be large enough that an adversary cannot solve discrete logarithms modulo $$p$$ (e.g. using the number field sieve). If $$p\approx 2^{2048}$$ NIST guidelines suggest that at least $$2^{112}$$ computational operations would be required. To find 2048-bit $$p$$, generate a random 1824-bit number $$m$$ and let $$p_0=q(2^{1824}+m)$$. Compute IsPrime($$p_0$$) and if successful let $$p=p_0$$ otherwise increment $$p_0$$ by $$q$$ and repeat until we are successful.

We now find $$\alpha$$. Let $$r=(p-1)/q$$ note that $$r$$ is an integer. Start with $$g=2$$. Compute $$\alpha_0\equiv g^r\pmod p$$, if $$\alpha_0\not\equiv 1\pmod p$$ take $$\alpha=\alpha_0$$, otherwise increment $$g$$ by 1 and repeat until successful.

The parameters are chosen to provide 112-bits of classical computational security, other parameters would provide different levels of security e.g. $$q\approx 2^{160}$$ and $$p\approx 2^{1024}$$ would provide about 80-bits of classical computational security and $$q\approx 2^{256}$$ and $$p\approx 2^{3072}$$ would provide about 128-bits of classical computational security.

• $t$ is interesting from a theoretical standpoint, but in practice $t$ and $q>2^t$ does not matter, since (as indicated in the answer) we need $\sqrt q$ to be large enough to foil BSGS and variants using less memory such a Pollard's rho.
– fgrieu
Sep 8 at 6:19