Advanced Digital Signatures

Certificates

A certificate is essentially a witness statement concerning one or more public keys. It is a common usage of digital signatures, but it is not a cryptographic primitive!

Certificates

A certification system specified conventions on who is allowed to issue certificates, the rules over their issuance (e.g. time limits and revocation) as well as their format and semantics.

For example, the certificate transparency protocol for TLS certificates helps protect against compromised Certificate Authorities.

Certificates in Web3

We are building systems that do not have a centralized "Certificate Authority".
But we can still use certificates to transfer some power from one key to another.

Multi-Signatures

We often want signatures that must be signed
by multiple parties to become valid.

Types of Multi-Signature

Trivial Multiple Signatures

• We assume that there is some verifier, who can check that some threshold of individual keys have provided valid signatures.
• This could be a trusted company or third party.
• For our purposes, "it's a blockchain."

Trivial Multiple Signatures

Trivial multiple signatures generally provide a good user experience, as no interaction is required from the participants.

Cryptographic Multi-Sigs

We want a succinct way to demonstrate that everyone from some set of parties have signed a message. This could be achieved purely on the signer side (without support from the verifier).

Key Generation for Multi-Sigs

In cryptographic multi-signatures,
signatures from individual public keys are aggregated. .

Each participant can choose their own key to use for the multi-signature.

Cryptographic Threshold Multi-Sigs

• Makes more compact signatures compatible with legacy systems.
• The public key is associated with a "threshold" number of signing parties.
• Not all parties are needed to take part in the signing process to create a valid signature.
• This requires MPC protocols and may need multiple rounds of interaction to generate the final signature.
• They may be vulnerable to DoS from a malfunctioning (or malicious) key-holder.

Key Generation - Threshold

• Threshold multi-signature schemes require that all signers run a distributed key generation (DKG) protocol that constructs key "shares".
• The secret encodes the threshold behavior, and signing demands some threshold of signature "fragments".
• This DKG protocol breaks other useful things, like hard key derivation.

Schnorr Multi-Sigs

Schnorr signatures are primarily used for threshold multi-sig.

• Fit legacy systems nicely, and can reduce fees on blockchains.
• Reduce verifier costs in bandwidth & CPU time, so great for certificates.
• Could support soft key derivations.

Schnorr Multi-Sigs - Downside

• However, automation becomes tricky.
• We need agreement upon the final signer list and two random nonce contributions from each prospective signer, before constructing the signature fragments.

BLS Signatures

• BLS signatures are especially useful for aggregated multi-signatures (but can be used for threshold as well).
• Signatures can be aggregated without advance agreement upon the signer list.
• This simplifies automation and makes them useful in consensus.
• Verifying individual signatures is slow, but verifying aggregated ones is relatively fast.
• (Coming to Substrate soonish.)

BLS Signatures

Allows multiple signatures generated under multiple public keys for multiple messages to be aggregated into a single signature.

BLS Signatures - Downside

• DKGs remain tricky (for threshold).
• Soft key derivations are typically insecure for BLS.
• Verifiers are significantly slower than Schnorr, due to using pairings, for a single signature.
• But for hundreds or thousands of signatures on the same message, aggregated signature verification can be much faster than Schnorr.

Schnorr and BLS Summary

Schnorr & BLS multi-signatures avoid complicating verifier logic,
but introduce user experience costs such as:

• DKG protocols
• Reduced key derivation ability
• Verification speed
• Proof of possession verification.

Ring Signatures

• Ring signatures prove the signer lies within some "anonymity set" of signing keys, but hide which key actually signed.
• Ring signatures come in many sizes, with many ways of presenting their anonymity sets.
• Anonymous blockchain transactions typically employ ring signatures (Monero, ZCash).