The definition and origin of Schnorr groups?

Question

Wanting to write something on Schnorr groups in a publication I realised how hard it is to find anything citable about them on the internet. Who can help me with the following questions?

1. What (and where) is the actual definition of a Schnorr group? Are all of its criteria fulfilled if it is a multiplicative finite cyclic group with a prime order? In the answer to What is a cyclic group of prime order q such that the DLP is hard? it sounds like it is only a Schnorr Group if the $r$ in $p = qr + 1$ is $r>2$?

2. Where have Schnorr groups first been introduced and who called them Schnorr groups? I checked the references in Security of Schnorr signature versus DSA and DLP, but I could not find anything useful in Schnorr's patents and his papers start off directly with:

   The KAC chooses primes $p$ and $q$ such that $q \mid p - 1, q \le 2^{214}, p > 2^{512}$, $\alpha \in \mathbb{Z}_p$ with order $q$, i.e., $\alpha^q = 1 \pmod{p}$, $\alpha \neq 1$

   So they already use Schnorr groups, but neither do they call them that nor do they give a procedure how to generate them. Which leads into my next question:

3. Where was a procedure to generate Schnorr groups first published? The Wikipedia article only gives a procedure without source, which is basically the same as in FIPS PUB 186-4, A.1 even though there it is not even called Schnorr group (proably due to patent reasons?).

UPDATE: Digging deeper I found this in PS96:

results for other signature schemes like Schnorr's are considered as folklore results but have never appeared in the literature

"Folklore results"? Maybe that's why Schnorr groups are so difficult to grasp.

Answer 1

1. What (and where) is the actual definition of a Schnorr group?
2. Where have Schnorr groups first been introduced and who called them Schnorr groups?

I don't know who first used the term—the earliest use I can dig up quickly is actually the Wikipedia article, initially drafted in November 2004 by Paul Crowley[1], who also used it a year earlier on sci.crypt[2]. What it means is a subgroup of prime order $q$ of the multiplicative group of the finite field $\mathbb Z/p\mathbb Z$, where $p$ is large enough (say 2048 bits) to resist index calculus on the field and $q$ is large enough (say 256 bits) to resist Pollard's $\rho$ or other generic discrete log attacks on the subgroup.

Cryptosystems defined in terms of Schnorr groups usually do not involve furnishing adversaries with oracles for $h \mapsto h^x$ for secret $x$, so minimizing $(p - 1)/q$ is not important as it is for, e.g., Diffie–Hellman; instead we make $q$ as small as we safely can to improve exponentiation performance. So usually we don't consider the order-$q$ subgroup of $(\mathbb Z/p\mathbb Z)^\times$ with a safe prime $p = 2q + 1$ to be a Schnorr group. But you wouldn't be disinvited from parties if you called it a trivial case of a Schnorr group with bad performance.

3. Where was a procedure to generate Schnorr groups first published?

The generation procedure—randomly choose prime $q$ of appropriate size, randomly choose $k$ of appropriate size until $p := kq + 1$ is prime, and randomly choose $h$ until you find a generator $g := h^k \not\equiv 1 \pmod p$—is obvious enough that it's easy to imagine that nobody bothered to write it down in a paper to publish in an academic venue.

results for other signature schemes like Schnorr's are considered as folklore results but have never appeared in the literature

What the ‘folklore’ comment means is that everyone tacitly felt they understood the result to be (perhaps intuitively or obviously) true, but nobody bothered to write a proof down or publish it, so there was nothing in the literature to formally cite.

Answer 2

Schnorr groups have been used by Schnorr in [Sc89a][Sc89b], [Sc90a][Sc90b], culminating with [Sc91]. These are the earliest detailed description of Schnorr groups of size relevant to cryptography that I could locate.

The groups are then used in DSA of FIPS186 in [Ni94], without attribution to Schnorr. Drafts reportedly circulated starting August of 1991, but that's well after the publication of [Sc89b] and the filing of [Sc90b]. James H. Burrows appears in the publication as director of the laboratory authoring DSA, but the actual author(s) are unknown to me. Many have hypothesized that DSA is a variant of Schnorr signature aimed as circumventing Schnorr's patents [Sc89a] [Sc90b] (I take no position on that).

In [HAC96], the group and its generation method is discussed as part of DSA.

In [PS96], the attribution is to Schnorr (the term "Schnorr group" is not used).

For the origin of "Schnorr group" itself, see Squeamish Ossifrage's answer.

---

[Sc89a]: Claus-Peter Schnorr, Method for subscriber identification and for generation and verification of electronic signatures in a data exchange system, EP0383985 in European Patent Register, 1989;
[Sc89b]: id., Efficient Identification and Signatures for Smart Cards, in proceedings of Crypto 1989;
[Sc90a]: id., Method for subscriber identification and for the generation and verification of electronic signatures in a data exchange system, EP0384475 in European Patent Register, 1990;
[Sc90b]: id., Method for identifying subscribers and for generating and verifying electronic signatures in a data exchange system, US Patent 4,995,082;
[Sc91]: id., Efficient Signature Generation by Smart Cards, in Journal of cryptology, 1991.

[Ni94]: NIST's Computer Systems Laboratory, in FIPS 186, 1994.

[HAC96]: Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone Handbook of Applied Cryptoraphy, 1996, section 11.5.1.

[PS96]: David Pointcheval, Jacques Stern, Security Proofs for Signature Schemes, in proceedings of Crypto 1996.