The Wonderful World of Digital Signatures: ECDSA, EdDSA, BLS, CL, Merkle, and so much more

Although we hardly ever use our wet signature, the methods we used with these are still around. We thus live in a fake digital signature…
Photo by Signature Pro on Unsplash

The Wonderful World of Digital Signatures: ECDSA, EdDSA, BLS, CL, Merkle, and so much more

Although we hardly ever use our wet signature, the methods we used with these are still around. We thus live in a fake digital signature world, and where your DocuSign signature looks more like the signature of Donald Trump than your own one. And when we look at signatures, what are we signing against? With our fake wet signatures, can we actually prove that the thing we are signing has not been changed? In Scotland, the PDF for vaccination status, for example, is an editable PDF document. It is all very much fake digital. Luckily, the App contained a signed version of vaccine status and which was digitally signed by the NHS.

The King of the Signatures: ECDSA

For all its faults, it is Bitcoin that shows the greatest potential for properly integrating digital signatures, and where we can base a trusted transfer of currency from one person to another. For this Satoshi selected the ECDSA (Elliptic Curve Digital Signature Algorithm), and used the secp256k1 curve. He/she perhaps just plucked it randomly, but it has worked well for over a decade and has been relatively free of problems (apart from developers not selecting random nonce values, of course). Ethereum, too, also uses ECDSA and secp256k1.

If you are interested in how ECDSA works, try here:

https://asecuritysite.com/signatures#sig1

If you are interested in the cracking methods for EDCDA, try here:

https://asecuritysite.com/signatures#sig2

The Rise of EdDSA and Curve 25519

But ECDSA and secp256k1 are not the only shows in town, and where EdDSA (Edwards curve DSA) and Curve 25519 are now being showcased in many new crypto methods. It can be seen in the IOTA network and in new VPN protocols, such as WireGuard.

Curve 25519 is actually named after the prime number it uses: 2²⁵⁵-19. This gives 128-bit security, and which should be enough for most applications. For those wanting even more security, we can use Curve 448, and which gives us 256-bit security, and not even the processing resources of every computer on the planet could crack that. Its name also derives from its prime number: 2⁴⁴⁸−2²²⁴−1 (the Goldilock’s prime).

If you are interested in how EdDSA works, try here:

https://asecuritysite.com/signatures#sig3

Merging Signatures: Meet Schnorr

But what happens if we have multiple signers? With ECDSA we would have to take the private key of all of the singers, and add their signature to the data. This would be inefficient in most cases (as the signing part would probably have more data than the actual transaction), and it would require a good deal of processing to check all the signatures. An improvement to this is to merge signatures together in a single entity and where we can produce one signature which is an aggregation of the signatures of the signers. For this, we have the Schnorr signature method, and which basically sums the signatures to produce a single signature, and which can then be easily tested against the public key of the signers.

If you are interested in how Schnorr signatures work, try here:

https://asecuritysite.com/signatures#sig5

Bitcoin now integrates these methods using Multi-sig (MuSig).

Keeping Privacy and Trust

In some applications, we may not want to give away the fact that we have signed for something, in order to preserve our privacy. But how can we still trust the signature? Well, with this we can implement signing methods that allow for an anonymous credential system. For example, we may trust the NHS to prove that someone is over 18 years old, and allow each GP to prove this for a person. With an anonymous signer, we can trust the signer, but we do not reveal who the signer is. These methods use often crypto pairing and which has two elliptic curves at their core. For this we have signatures such as CL (Camenisch-Lysyanskaya) and BLS (Boneh–Lynn–Shacham).

If you are interested in how the privacy-preserving signatures work, try here:

https://asecuritysite.com/signatures#sig7

These types of signatures allow us to extract parts of our credentials, and still create a valid signature. For example, the NHS could sign credentials for our date-of-birth and our vaccine details, and where we could just extract the date-of-birth as a credential to present to a requestor, and for the signature to be valid from the NHS.

RSA just keeps plodding on

And don’t forget good old RSA. It is still around and is still used with digital certificates signatures. For this, we sign the digital certificate with the private key of the trusted party (eg Let’s Encrypt), and everyone can then prove the signature on the certificate with their public key. The most common method for this is RSA signing and DSA (Digital Signature Algorithm), and where is an example from a digital certificate is:

If you are interested in how the RSA signatures work, try here:

https://asecuritysite.com/signatures#sig9

Ring signatures

And for privacy, we may want to sign with multiple keys, but preserve the privacy of the true signer. In this way, we can trust the signature, but not know who it is that signed it. This is the method that some privacy-preserving cryptocurrencies use, and where we gather together the public keys of users with a similar spending profile, and then add these to the ring for signing. Only the person who is signing for the transaction needs their private key for the signature (the others have their public key added).

If you are interested in how ring and group signatures work, try here:

https://asecuritysite.com/signatures#sig10

Quantum robust signatures

Well, elliptic curve and RSA methods can both be cracked by quantum computers, so a number of quantum robust methods are being investigated for standardization. One of these is the usage of hash-based signatures, and where we can have many private keys, and then reveal each one for a new signing. Our public key becomes the proof that we can show that these private keys all lead to our public key.

If you are interested in how hash-based signatures work, try here:

https://asecuritysite.com/signatures#sig12

Other methods for quantum robust signatures include lattice, and Oil-and-Vinegar. If you have interested in these methods, try here:

https://asecuritysite.com/signatures#nist2

Conclusions

And so? Let’s build a more trusted digital world, and move away from our world of wet signatures. While human trust is the key to building this, we need to make sure we are building on maths, and not on sand.