Schnorr signatures for dummies

There has been a lot of hype about Schnorr signatures lately. The reason being that the patent expired few years ago and numerous people are working on using them instead of ECDSA.

If you are not familiar with math lingo, however, it may not be obvious what Schnorr signatures are and how they work. In this article I’ll try to demystify this signature scheme.

Cryptographic signature

To understand cryptographic signature, you need to understand what real signature are used for. A signature is put on a document to identify its author, or as a way to signal approbation. Or, in more abstract terms, a signature is a way to associate an identity and a document. The document is usually called message in cryptography.

In order to prove identity, we need something that only a specific actor (usually called Alice) can produce, but that everybody can verify. In addition, we want this to be attached to a specific message such as if the message is modified, the signature becomes invalid. This way, someone cannot reuse Alice’s signature on other documents than the one she signed.

Hash function

A hash function is a function that takes a message as input, and produce a fixed size output, usually called hash or digest. For a hash function to be used in cryptography, it must be a one way function, which means that knowing a hash do not provide any information about the message and needs to be collision free, meaning that there is no known way to find 2 messages sharing the same hash.

Elliptic curve cryptography

For Alice and only Alice to be able to produce the signature, we need to use a mathematical problem that is easy in one direction but impossibly hard in the other direction, unless you know some secret. It needs to be easy in one direction so that everybody can verify the signature, but very hard in the other so that nobody – but Alice – can produce the signature. It needs to still be possible if one knows a secret so Alice, who know the secret, can produce the signature. Such a mathematical process is called a trapdoor function.

Going into the details of elliptic curves isn’t the goal of this article, however, some basics are required to understand how they can be used to create a trapdoor function.

Eliptic curves, like all curves are made of points. However, it is possible to define an addition operation on these points that share many of the additions properties of integers. This also means that a point on the curve can be multiplied by an integer, by adding it to itself many times. For instance, P + P + P = 3 * P .

The mathematics of elliptic curves are such as it is easy, given P and the number 3 to compute 3 * P, but it is not possible, given P and Q with Q = 3 * P to find out that Q is in fact 3 * P . Now we have a trapdoor function. Let see how it is used in practice.

Alice and Bob will agree on a signature process, which involve a specific elliptic curve, a point on the curve called G. Alice will chose a random number x and will keep it secret. She will then compute P = x * G and will publish P to the world and keep x secret. Knowing P and G, there is no way for anyone else to find what x is.

x is Alice’s private key, and P is Alice’s public key.

Alice and Bob now need a process that only Alice can execute because it requires knowledge of x, but that everybody can verify as the verification only involve P. This way, everybody can be certain that only Alice could have produced the signature. This is where Schnorr signature comes in.

Schnorr

At its core, Schnorr signatures use a particular function, defined as

[cc]H'(m, s, e) = H(m || s * G + e * P)[/cc]

H is a hash function, for instance SHA256.
s and e are 2 numbers forming the signature itself.
m is the message Alice wants to sign.
P is Alice’s public key.

To verify the signature, Bob checks that the result of H'(m, s, e) is equal to e. Note that this is quite a feat to produce such a result. e is used to compute the hash itself, so having the result of the hash being e is somewhat of a paradox. It means that Alice was somehow able to chose s such as e is not involved in the calculation of the hash anymore.

To anyone but Alice, this is impossible to do. But Alice knows a secret. She knows that P = x * G . Therefore, she knows that

[cc]H'(m, s, e) = H(m || (s + e * x) * G)[/cc]

Alice is going to choose a number k, and compute e = H(m || k * G) . She has her value e, and now needs to determine what value of s is appropriate. Hopefully, she knows that thing will work out if k = s + e * x, so she can compute s = k – e * x and send e and s to Bob.

Generating the signature require knowledge of x. Therefore we know that only Alice can have generated that signature. On the other hand, anybody can verify the signature using Alice’s public key. Finally, the message is hashed in the process of creating the signature, so any modification of the message will invalidate the signature.

It has to be noted that Alice needs to be using new values of k every time. If not, Eve can use several of Alice’s signatures to recover her private key.

[cc]
k = s0 + e0 * x = s1 + e1 * x
x = (s0 – s1) / (e1 – e0)
[/cc]

There are various strategies for Alice to make sure she isn’t reusing the same value for k, for instance, using k = H(m || x) makes k both unpredictable for anyone who do not know x and will ensure a new k is used for every messages.

Ring signatures

Ring signatures are a cryptographic tool which allow for any actor in a group to sign, without revealing which actor did. The idea was introduced as a tool for whistleblower but is now most importantly used for anonymous cryptocurrencies such as Monero for the anonymity it provides.

To make the example simple we will only use 2 actors, Alice and Bob. Alice’s public key is P0 = x0 * G and Bob’s is P1 = x1 * G. The proof will be composed of (e0, s0, s1). To verify the signature, Carol will run a round of Schnorr per public key, feeding the value found for e at each round into the next one. If the last value for e equal the first one, then it means that someone along the way was used its private key to close the ring.

[cc lang=”d”]
e = firste;
for (int i = 0; i < actors; i++) { e = H(m || s[i] * G + e * P[i]); } assert(e == firste); [/cc] It is impossible for Carol to know who signed, just that one of these public key signed. Both Alice and Bob can produce a valid signature. To do so, Alice will chose a value for k and compute e1 = H(m || k * G). She will then chose a random value s1 and use it to compute e0 = H(m || s1 * G + e1 * P1). Now that she has e0, she can compute s0 = k – e0 * x0 and close the ring. Bob can do the same, but starting at index 1, computing e0 = H(m || k * G) then chose a random value for s0 and compute e1 = H(m || s0 * G + e0 * P0). Now that he has e1, he can compute s1 = k – e1 * x1.

The idea can be generalized to as many actors as we want, and will produce a proof of the form (e, s0, s1, …, sn) for n actors.

Conclusion

Schnorr signatures are both a fairly simple signature scheme yet very powerful at the same time. This simplicity translate to fast implementations as Schnorr signatures, contrary to ECDSA, do not require expensive operation such as inverse. It can be extended to support more advanced signatures systems such as ring signatures.

2 thoughts on “Schnorr signatures for dummies

  1. Pingback: Schnorr signatures for (not so) dummies | Deadalnix's den

  2. Pingback: SegWit and technologies built on it are grossly oversold | Deadalnix's den

Leave a Reply

Your email address will not be published. Required fields are marked *