Replying to Avatar waxwing

Interesting to observe that Schnorr's protocol for proving knowledge of discrete log (which for the TLDR people is kind of the "primitive" behind the Schnorr signature) is really actually a tweak on a pre-existing idea from a paper by Chaum, Evertse and van de Graaf in '87.

https://link.springer.com/content/pdf/10.1007/3-540-39118-5_13.pdf

Specifically the construction `s = k + ex` is already present in that work. The main tweak is that Schnorr proposes the variable `e` being a "full" random group element, whereas that paper proposes iterations with `e` being only a bit. It's the same basic thing.

Schnorr actually references it in his original paper on "Efficient Identification and Signatures for Smart Cards", and he also develops the idea more than that, so I'm not accusing of plagiarism or something; just pointing out yet another reason why having a patent on this is so stupid.

(I mean patent aside, it's also of historical interest. Yet another example of Chaum being "the GOAT" as the kids say).

Of course that begs the question what came before Chaum :-)

Reply to this note

Please Login to reply.

Discussion

Absolutely :) ... except for a lot of the stuff Chaum published in the 80s, it really was breaking new ground.

Apparently this paper was published while he was working at an academic institute in the Netherlands, I guess he was doing that for a few years before deciding to try to "monetize" in the early 90s sometime and hence digicash being there.

Fwiw I did go another step "up the tree" by looking at the references of that paper, and it seems the only real precursor is another one by the same authors, one year previous:

https://core.ac.uk/download/pdf/301667381.pdf

see p.206-207 : these are two protocols doing the same thing (proving DL), but they are a little less elegant than the later ones. That paper itself is "the root" (or at least one such), if you take the authors at face value. Quote: "As far as we know, no other protocol with the same functionality has been presented."

It seems like this line of research came directly out of the Goldwasser, Micali, Rackoff paper in '85 showing that ZKPs are possible; they reference that set of ideas heavily here.