Very short signatures that can be squashed together: thousands of signatures become one.
The idea: Your private key is a secret number a. Your public key is a·G on a curve. To sign, hash the message to a curve point H and multiply it by a. A pairing lets anyone check that the signature and the public key were made with the same a, without learning it. Because signing is just multiplying by a secret, signatures from many people add up into one point, and thousands of signatures on the same message are checked almost as fast as one.
Why it matters: Lets blockchains like Ethereum check huge numbers of votes cheaply.
The details
On the map: short, aggregatable
Short signatures that can be aggregated[1, 2]: thousands of signatures on the same or different messages compress into one. Signatures can be as small as 48 bytes on BLS12-381. Security rests on co-CDH, with the hash-to-curve function modeled as a random oracle (ROM)[3, 4].
Where you meet it: proof-of-stake consensus (Ethereum validators), threshold randomness beacons (drand)[5], Chia and Filecoin.
Nothing on the map depends on it: it is an end point, something people use directly.
About the tags
ROM
Its security proof treats a hash function as a perfectly random function (the random oracle model). Real hashes aren't random functions, so this is a heuristic. For signatures and encryption no practical attack has exploited it. For multi-round proof systems, see the Fiat-Shamir box.
References
Dan Boneh, Ben Lynn and Hovav Shacham. Short Signatures from the Weil Pairing. Journal of Cryptology, 2004. doi:10.1007/s00145-004-0314-9
Dan Boneh, Craig Gentry, Ben Lynn and Hovav Shacham. Aggregate and Verifiably Encrypted Signatures from Bilinear Maps. Advances in Cryptology — EUROCRYPT 2003. doi:10.1007/3-540-39200-9_26
A. Faz-Hernandez, S. Scott, N. Sullivan et al. Hashing to Elliptic Curves. RFC 9380, 2023. rfc-editor.org/rfc/rfc9380