0
$\begingroup$

I have currently started a course on cryptography and am an absolute beginner. While reading through Schnorr's Protocol I came across several ways in which it was described.

One of the approach is described here: - https://www.youtube.com/watch?v=mV9hXEFUB6A

A second approach using discrete logarithmic is described here - https://asecuritysite.com/encryption/schnorr

The third article had a slightly different mathematics to the discrete log implementation- https://blockgeeks.com/guides/what-is-zksnarks/#The_Schnorr_Identification_Protocol

I apologize if this is completely novice. I just want to know how are they different and which protocol was initially published by Claus Schnorr?

edit: Thanks for the reply. My main doubt is while learning Schnorr's signature, The implementation on the Asecurity source given and the Blockgeeks source given is different. What is the difference between them? What Asecurity says:

With Schnorr identification, Peggy (the prover) has a proving public key of (N,g,X)(N,g,X) and a proving secret key of (N,x)(N,x). NN is a prime number for the modulus operation, and xx is the secret, and where:

X←gx(modN)X←gx(modN)

On the registration of the secret, Peggy generates a random value (yy), and then computes YY:

Y←gy(modN)Y←gy(modN)

This value is sent to Victor (who is the verifier). Victor then generates a random value (c)(c) and sends this to Peggy. This is a challenge to Peggy to produce the correct result. Peggy then computes:

z←(y+xc)(modN)z←(y+xc)(modN)

He then sends this to Victor in order to prove that he knows xx. Victor then computes two values:

val1=YXc(modN)val1=YXc(modN)

val2=gz(modN)val2=gz(modN)

If the values are the same (val1≡val2val1≡val2), Peggy has proven that she knows xx.

This works because:

YXc=gygxc=gy+cxYXc=gygxc=gy+cx

gz=gy+cxgz=gy+cx

Blockgeeks

Anna wants to prove to Carl that she knows a value x such that y = g^x to a base g.

Anna picks a random value v from a set of values Z, and computes t = g^v.

Anna computes c = H(g,y,t) where H() is a hash function.

Anna computes r = v – c*x.

Carl or anyone can then check if t = g^r * y^c.

Improve this question
$\endgroup$
  • $\begingroup$ FWIW, a re-description of the original scheme is in the section "Original Schnorr signature scheme" there.and perhaps could help, even though I apologize this is not at the entry level. There's also a bibliography about Schnorr signature with link to the original. One thing is sure: all the many variants of Schnorr Signature have their security based of the hardness of the Discrete Logarithm Problem in some group. $\endgroup$ – fgrieu♦ May 31 '20 at 21:42
  • $\begingroup$ Hi. I had already been through it before. I am confused on what is the difference between the above approaches? Can the discrete logarithmic approach not be used to sign very a message? Who introduced the discrete approach(I could not find it). Also what is the difference between the two discrete approaches stated. $\endgroup$ – ciberexplosion May 31 '20 at 22:09
  • $\begingroup$ Repeating an equation twice, without a space in between, does not help. Latex/Mathjax does. From what I can decipher, neither of the two things there are signature; they are zero-knowledge proof. There also are notational differences (different letters for similar quantities, implicit modulo in the second, exponent garbled in pasta for the first). There might be a difference of sign (Schnoor uses the efficient way where the sign issue is dealt as key generation, regurgitations not all do). $\endgroup$ – fgrieu♦ Jun 1 '20 at 9:18
  • $\begingroup$ Suggestion: read the original paper. It goes from the bottom up so that the audience, which then had not heard about Schnoor identification protocol or signature, can get them. At least, there is no question about it being a variant or not. Except that the parameters need to be sized up to resit more than a few CPU×days of effort (to 256 where there is 140, 2048 where there is 512, 128 where there is 72), it's still perfectly OK, despite decades of effort to break or prove it, ending essentially in the later. That's a feat! $\endgroup$ – fgrieu♦ Jun 1 '20 at 9:37
1
$\begingroup$

The first publication using the Discrete Logarithm Problem (DLP) for asymmetric cryptography is in Diffie-Hellman key exchange. The original works in the multiplicative group $\Bbb Z_p^*$, or a typically large subgroup of that.

The first use for signature is ElGamal signature. It uses the same kind of groups, and that makes its signature rather large. It does not use a hash. That and other issues make the original description unsatisfactory; it's more a building block for later signature schemes based on the DLP.

The most notable is the original Schnorr signature. It works in a slightly different group, called Schnorr group, which is a small subgroup of $\Bbb Z_p^*$, with $q$ elements where $q$ is a prime dividing $p-1$, and much less wide/large. That provides what long was (and if we restrict to practice, remains) the shortest known secure signature with appendix (that is, added to the unmodified message): $3b$-bit signature for $b$-bit security. The signature consists of a $b$-bit hash and an integer modulo $q$ over $2b$ bits.

A variant differing only by using a $2b$-bit hash is cleaner from a math standpoint and slightly less difficult to prove secure, thus was much studied, and is stated as being Schnorr signature in many textbooks. That one has a $4b$-bit signature, for a group with a little less than $2^{2b}$ elements. The exposition in the HAC is among these, and it's signature has the hash second, contrary to the original. It is followed by an example with small integers.

The later DSA of FIPS 186 is often seen as a way to work around Schnorr's patent. It is significantly different and more complex. It has $4b$-bit signature.

There are many later signatures also called Schnorr signature, typically with $4b$-bit signature, also based on the DLP, but in an Elliptic-curve group. Study these later!

  • "original Schnorr signature" unambiguously means a scheme in a Schnorr group, with $3b$-bit signature having one component a $b$-bit hash, the other $2b$-bit coding an integer.
  • "Schnorr signature" can be any number of things. In introductory material that could be either the original, or the variant where the hash is made $2b$-bit. Other possibilities are too many to enumerate.

Note: "Discrete logarithmic Schnorr Signature" is a naming error. "Logarithmic" is an adjective applying to quantities, mostly continuous. A complexity can be logarithmic, perhaps by extension a count including the bit length of a bitsring, rather not a bitstring like signatures are, not a signature scheme which is a method to obtain and verify a signature. Make that: "Schnorr signature" (thus) based on the Discrete Logarithm Problem (in some group).

Remark: some videos are a great way to learn for their author.

Improve this answer
$\endgroup$
  • $\begingroup$ I am still not a bit clear. I have edited my answer for better explanation of my question. $\endgroup$ – ciberexplosion Jun 1 '20 at 8:12

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.