This question arises because I couldn't find any official paper for the Schnorr identification scheme, but only for the Smart-Card implementation of it. Also, it seems that everyone, when talking about the SIS links the paper for the Smart-Card implementation. So I'm kinda confused, especially 'cause English isn't my native language and I can't figure it out by myself. I don't understand if they are the same thing, or if they differ just for a simple particular reason that didn't need a dedicated paper. If so... what's that difference? Thank you very much!
The standard paper used as reference for the Schnorr identification protocol and associated signature scheme is Claus-Peter Schnorr, Efficient Signature Generation by Smart Cards (alternative version), in Journal of Cryptology, 1991.
Differences between this and the Schnorr identification protocol as in a modern textbook:
The original exposition uses a Schnorr group of large prime order $q$, that is a subgroup of the group $\mathbb Z_p^*$ for a huge prime $p$ with $q$ a divisor of $p-1$. It's now customary to reason in an abstract group of order $q$, which can be implemented e.g. as an elliptic curve group.
The group's notation is multiplicative in the original, and is now often additive.
In the original, the verifier's secret $e$ is random in $[0,2^t)$ with $2^t\ll q$, for efficiency reasons. Many modern expositions make $e$ random in $[0,q)$ or similarly large interval.
The original is unclear about if in the identification protocol itself the prover A sends group element $x$ (text) or it's hash $h(x)$ (figure 1), an optimization reducing communication size. Modern expositions tend to use no hash in the identification protocol.
- in 2.: “…the KAC’s signature $S$ for $(I,v)$,…”
- in 3.: “B verifies the signature $S$…”
- in 5.: “B verifies $(I,v)$ either by checking the signature $S$ or by verifying $(I,v)$ on–line”.
But modern expositions often make that an external preliminary. Some remove $I$ and $S$, and A supplying it's public key $v$ in the first step.
In some parts of the original article A is a Smart Card, when some other expositions are mum on how computations are made, or assimilate computation means with their owner/operator.
The original exposition emphasizes that A drawing $r$ and computing $x$ (in step 2.) can be an offline preliminary.
Using the original notation and steps numbering (contrary to many textbooks), a minimal modern exposition could go
- We work in a suitable public group of prime order $q$ and generator $\alpha$, noted multiplicatively. The group's $q$ elements are thus $\alpha^b$ for $b\in[0,q)$.
- Prover A wants to demonstrate knowledge of $s\in[0,q)$ such that $v=\alpha^s$, with public $v$ assumed known to verifier B. It uses four exchanges:
- A draws $r\in_R[0,q)$, computes $x:=\alpha^r$, sends $x$
- B draws $e\in_R[0,q)$, sends $e$
- A computes $y:=r+s\,e\bmod q$, sends $y$
- B verifies $x=\alpha^y\,v^e$.
Is the Schnorr identification scheme and the Smart Card implementation actually the same identical thing?
No: a scheme is not an implementation, much like an algorithm is not the same as a program using that algorithm written for a particular type of computer. The implementation makes choices like the computing mean being a Smart Card; using a Schnorr group with certain size parameters; further limiting the number of bits in $e$ to parameter $t$. It sends hash $h(x)$ rather than $x$ in step 2, with the verification step 5 correspondingly changed to $h(x)=h(\alpha^y\,v^e)$. It defines what $v$ is in the context, and towards that introduces $I$ and $S$.
When a modern text refers to the Schnorr identification scheme, it tends to be to the abstract protocol reduced as in the above section, without Smart Card, $t$, $h$; and often without $I$, $S$.
In work making use of the Schnorr identification scheme, I'd cite the JoC paper and independently state the protocol I use, so that there's no ambiguity about what I mean with Schnorr identification scheme.