4
$\begingroup$

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!

$\endgroup$
4
  • $\begingroup$ link.springer.com/content/pdf/10.1007%2F3-540-45708-9_11.pdf and follow the references.. $\endgroup$
    – kelalaka
    Oct 24 at 20:27
  • $\begingroup$ I already did actually. I've already found this paper and here they link the Smart-Card implementation. $\endgroup$ Oct 24 at 20:35
  • $\begingroup$ Could you next time please provide links and textual references to the documentation you are mentioning in the question? $\endgroup$
    – Maarten Bodewes
    Oct 25 at 11:54
  • $\begingroup$ Of course, sorry $\endgroup$ Oct 25 at 12:50
6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thanks for the explanation, but my question was simpler: is the Shnorr identification scheme and the Smart Card implementation actually the same identical thing? That's the part I can't really tell 'cause english isn't my native language... But I did understand the actual protocol without looking at the paper, I just need to figure out if those are two different things and something changes, or there's just "one" schnorr identification scheme and the Smart Card thing is just the context, because I have to cite the paper. $\endgroup$ Oct 25 at 6:45
  • 1
    $\begingroup$ You're putting way too much stock into the paper's title. The linked paper is the journal version of the paper that introduced Schnorr signatures. There's an older conference version as well. One or both is what you would cite. As @fgrieu explained the exact instantiation is likely not what people mean when they refer to Schnorr signatures or the Schnorr identification scheme but it's nevertheless the work that introduced them. The smart card bit was nothing more than an early 90s sales pitch for an efficient signature scheme. $\endgroup$
    – Maeher
    Oct 25 at 14:48
  • $\begingroup$ Thank you very much to both of you, now everything's clear! Thanks @fgrieu $\endgroup$ Oct 25 at 17:55

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.