The Shortest Signatures Ever (2016) [pdf]

eprint.iacr.org

27 pointsbeefhash4 comments

Curious there is no reference to the BLS Short Signature scheme.

While pairing-based cryptography is not quantum resistant (yet? Can we mix in isogenies in there?), the signature, secret keys and public keys are really small, for example with a 256-bit prime we're looking at 256-bit secret keys and 256-bit or 512-bit public keys/signatures (you can choose which one is bigger/slower depending on what you want to prioritize).

It is also going into standardization right now:

- https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-00

and will be a standard adopted across several blockchains (Algorand, Chia Network, Dfinity, Ethereum 2.0, Filecoin, Zcash to name those I am aware of).

The signatures may be small (344 bits) but the keys are huge (tens to hundreds of kilobytes).

By itself that's a good trade if you need vastly more signatures than keys. I can imagine package management tools would accept much larger keys (maybe you have a dozen keys total in use at any time) for smaller signatures (every single package and metadata update needs signing).

Of course other factors may dominate anyway.

Big keys have significant practical consequences. You cannot distribute them as QR codes, for example.

Reply on news.ycombinator.com