What's the main difference between the Schnorr identification scheme and its Smart-Card implementation?

Question

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!

Answer 1

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.

• The original (in both text and figure 1) makes it part of the identification protocol to verify A's public key $v$ and it's association with A's identity $I$ using a signature $S$:

  • 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:
  • 2. A draws $r\in_R[0,q)$, computes $x:=\alpha^r$, sends $x$
  • 3. B draws $e\in_R[0,q)$, sends $e$
  • 4. A computes $y:=r+s\,e\bmod q$, sends $y$
  • 5. 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.