BLS digital signature
The scheme uses a bilinear pairing for verification, and signatures are elements of an elliptic curve group. Working in an elliptic curve group provides some defense against index calculus attacks (with the caveat that such attacks are still possible in the target group of the pairing), allowing shorter signatures than FDH signatures for a similar level of security.
Signatures produced by the BLS signature scheme are often referred to as short signatures, BLS short signatures, or simply BLS signatures. The signature scheme is provably secure (the scheme is existentially unforgeable under adaptive chosen-message attacks) in the random oracle model assuming the intractability of the computational Diffie–Hellman problem in a gap Diffie–Hellman group.
A gap group is a group in which the computational Diffie–Hellman problem is intractable but the decisional Diffie–Hellman problem can be efficiently solved. Non-degenerate, efficiently computable, bilinear pairings permit such groups.
Let be a non-degenerate, efficiently computable, bilinear pairing where , are groups of prime order, . Let be a generator of . Consider an instance of the CDH problem, ,, . Intuitively, the pairing function does not help us compute , the solution to the CDH problem. It is conjectured that this instance of the CDH problem is intractable. Given , we may check to see if without knowledge of , , and , by testing whether holds.
By using the bilinear property times, we see that if , then, since is a prime order group, .
BLS signature scheme
- Key generation
The key generation algorithm selects a random integer such as . The private key is . The holder of the private key publishes the public key, .
Given the private key , and some message , we compute the signature by hashing the bitstring , as . We output the signature .
Given a signature and a public key , we verify that .
- Simple Threshold Signatures
- Signature Aggregation: Multiple signatures generated under multiple public keys for multiple messages can be aggregated into a single signature.
- Unique and deterministic: for a given key and message, there is only one valid signature (like RSA PKCS1 v1.5, EdDSA and unlike RSA PSS, DSA, ECDSA and Schnorr).
- Chia blockchain currently uses BLS signatures
- By 2020, BLS signatures were used extensively in version 2 (Eth2) of the Ethereum blockchain, as specified in the IETF draft BLS signature specification—for cryptographically assuring that a specific Eth2 validator has actually verified a particular transaction. The use of BLS signatures in Ethereum is considered a solution to the verification bottleneck only for the medium term, as BLS signatures are not quantum secure. Over the longer term—say, 2025–2030—STARK aggregation is expected to be a drop-in replacement for BLS aggregation.
- Barreto, Paulo S. L. M.; Kim, Hae Y.; Lynn, Ben; Scott, Michael (August 2002). "Efficient Algorithms for Pairing-Based Cryptosystems". Advances in Cryptology — CRYPTO 2002. CRYPTO '02: Proceedings of the 22nd Annual International Cryptology Conference on Advances in Cryptology. Springer-Verlag Berlin Heidelberg. pp. 354–369. doi:10.1007/3-540-45708-9_23.
- "Ethereum 2.0 Phase 0 -- The Beacon Chain : BLS Signatures". 28 July 2020. Retrieved 4 September 2020.
- Dan Boneh; Ben Lynn & Hovav Shacham (2004). "Short Signatures from the Weil Pairing". Journal of Cryptology. 17 (4): 297–319. CiteSeerX 10.1.1.589.9141. doi:10.1007/s00145-004-0314-9. S2CID 206885645.
- D. Boneh, C. Gentry, H. Shacham, and B. Lynn Aggregate and Verifiably Encrypted Signatures from Bilinear Maps, proceedings of Eurocrypt 2003, LNCS 2656, pp. 416-432, 2003
- Drake, Justin (5 December 2019). "Pragmatic signature aggregation with BLS". ethresear.ch/. Eth research. Retrieved 8 January 2021.