In some applications like QR-codes, saving 25 bytes out of 100 makes a difference in usability.
What choice is there for a signature scheme with (most important criteria first)
- As small as possible signature size (for a signature with appendix) or as small as possible added size (measured at 40-byte arbitrary message for a signature scheme with message recovery, but I'd prefer avoiding these), at conjectured 128-bit security level (effort to break comparable to AES-128 key search) discounting Cryptographically Relevant Quantum Computers.
- Standardized or vetted by ISO, IEC, ETSI, ANSI, ECRYPT, NIST, ANSSI, BSI, SECG, CFRG, some national standard or body, unamit…, or even an active IETF RFC or a reasonable consensus of crypto experts.
- Not or no longer patent-encumbered.
- Not overly resource-intensive for verification (perhaps use DSA-3072-256 as the limit).
So far I see:
Notably absent is short Schnorr signature (on Elliptic Curve or Schnorr group), which would be about 48-byte, but AFAIK fails [2]. Perhaps it was not standardized because it has slightly worrying security characteristics:
- The best brute force attack on the hash alone (e.g. with ASICs as in bitcoin mining) obtains with probability $1/n$ a signed message of practical content at cost $2^{128}/n$ hashes and one merely known message/signature pair, versus cost $\sqrt n$ times higher and one signature query with chosen message for 64-byte competitors.
- The private-key holder can generate pairs of messages with different and practical content but the same signature using about $2^{66}$ hashes.
¹ I think people got cold feet after the Extented Tower Number Field Sieve incited to revise down earlier security estimates of pairing-friendly curves formerly thought secure, and change some deployed schemes. The subject has grown so complex I'm unable to follow, but from what appears to be a one-page summary of the latest estimates around, for 128-bit security, BLS12-381 at best has not much margin and BN254 seems at risk, in at least some applications (I don't know for BLS signature).