BLS digital signature

A BLS digital signature, also known as Boneh–Lynn–Shacham^[1] (BLS), is a cryptographic signature scheme which allows a user to verify that a signer is authentic.

The scheme uses a bilinear pairing $e:G_{1}\times G_{2}\to G_{T}$ , where $G_{1},G_{2},$ and $G_{T}$ are elliptic curve groups of prime order $q$ , and a hash function $H$ from the message space into $G_{1}$ . Signature are elements of $G_{1}$ , public keys are elements of $G_{2}$ , and the secret key is an integer in $[0,q-1]$ . 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 $G_{T}$ 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.^[2] 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.^[1]

BLS signature scheme

A signature scheme consists of three functions: generate, sign, and verify.^[1]

Key generation

The key generation algorithm selects the private key by picking a random integer $x\in [0,q-1]$ . The holder of the private key publishes the public key, $g_{2}^{x}$ , where $g_{2}$ is a generator of $G_{2}$ .

Signing

Given the private key $x$ , and some message $m$ , we compute the signature by hashing the bitstring $m$ , as $h=H(m)$ , and we output the signature $\sigma =h^{x}$ .

Verification

Given a signature $\sigma$ for message $m$ and public key $g_{2}^{x}$ , we verify that $e(\sigma ,g_{2})=e(H(m),g_{2}^{x})$ .

Properties

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).^[3]
Signature Aggregation: Multiple signatures generated under multiple public keys for multiple messages can be aggregated into a single signature.^[4]
Simple Threshold Signatures^[5] and multisignatures.^[6]

Curves

BLS12-381

BLS12-381 is part of a family of elliptic curves named after Barreto, Lynn, and Scott^[7] (a different BLS trio, except for the L). Designed by Sean Bowe in early 2017 as the foundation for an upgrade to the Zcash protocol. It is both pairing-friendly (making it efficient for digital signatures) and effective for constructing zkSnarks.^[8] The usage of BLS12-381 for BLS signatures is detailed in the IETF internet draft^[9]

Implementations

Chia network has used BLS signatures.^[10]^[11]
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.^[2] 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.^[9]^[12]
Dfinity (developers of the "Internet Computer" cryptocurrency) uses a BLS implementation.^[13]
Skale cryptocurrency uses BLS signature algorithm.^[14]
drand uses the BLS12-381 curve as a threshold scheme.^[15]

References

^ ^a ^b ^c 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.
^ ^a ^b "Ethereum 2.0 Phase 0 -- The Beacon Chain : BLS Signatures". GitHub. 28 July 2020. Retrieved 4 September 2020.
^ Shacham, Hovav. "New Paradigms in Signature Schemes" (PDF). www.semanticscholar.org. p. 18. Retrieved 2024-06-07.
^ 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
^ Craige, Jake (11 March 2020). "Threshold BLS Signatures". jcraige.com. Retrieved 8 August 2022.
^ Boldyreva, Alexandra (2002). Desmedt, Yvo G. (ed.). "Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme". Public Key Cryptography — PKC 2003. Berlin, Heidelberg: Springer: 31–46. doi:10.1007/3-540-36288-6_3. ISBN 978-3-540-36288-3.
^ Barreto, Paulo S. L. M.; Lynn, Ben; Scott, Michael (2003), "Constructing Elliptic Curves with Prescribed Embedding Degrees", Security in Communication Networks, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 257–267, ISBN 978-3-540-00420-2, retrieved 2024-02-11
^ "BLS12-381 For The Rest Of Us". HackMD. Retrieved 2024-02-11.
^ ^a ^b Boneh, Dan; Gorbunov, Sergey; Wahby, Riad S.; Wee, Hoeteck; Wood, Christopher A.; Zhang, Zhenfei (2022-06-16). BLS Signatures (Report). Internet Engineering Task Force.
^ "5. BLS Signatures | Chia Documentation". docs.chia.net. Retrieved 2023-06-07.
^ BLS signatures
^ Drake, Justin (5 December 2019). "Pragmatic signature aggregation with BLS". ethresear.ch/. Eth research. Retrieved 8 January 2021.
^ "Chain-key signatures | Internet Computer". internetcomputer.org. Retrieved 2024-08-16.
^ "SKALE Documentation :: SKALE Network Documentation". docs.skale.network. Retrieved 2024-08-16.
^ "2.1 Cryptography". drand. Retrieved 2024-11-18.

External links

[BLS2004-1] 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.

[Eth2spec20200904-2] "Ethereum 2.0 Phase 0 -- The Beacon Chain : BLS Signatures". GitHub. 28 July 2020. Retrieved 4 September 2020.

[3] Shacham, Hovav. "New Paradigms in Signature Schemes" (PDF). www.semanticscholar.org. p. 18. Retrieved 2024-06-07.

[BGSL2003-4] 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

[jcraige20200311-5] Craige, Jake (11 March 2020). "Threshold BLS Signatures". jcraige.com. Retrieved 8 August 2022.

[6] Boldyreva, Alexandra (2002). Desmedt, Yvo G. (ed.). "Threshold Signatures, Multisignatures and Blind Signatures Based on the Gap-Diffie-Hellman-Group Signature Scheme". Public Key Cryptography — PKC 2003. Berlin, Heidelberg: Springer: 31–46. doi:10.1007/3-540-36288-6_3. ISBN 978-3-540-36288-3.

[7] Barreto, Paulo S. L. M.; Lynn, Ben; Scott, Michael (2003), "Constructing Elliptic Curves with Prescribed Embedding Degrees", Security in Communication Networks, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 257–267, ISBN 978-3-540-00420-2, retrieved 2024-02-11

[:0-8] "BLS12-381 For The Rest Of Us". HackMD. Retrieved 2024-02-11.

[:1-9] Boneh, Dan; Gorbunov, Sergey; Wahby, Riad S.; Wee, Hoeteck; Wood, Christopher A.; Zhang, Zhenfei (2022-06-16). BLS Signatures (Report). Internet Engineering Task Force.

[10] "5. BLS Signatures | Chia Documentation". docs.chia.net. Retrieved 2023-06-07.

[11] BLS signatures

[ethresearch20191205-12] Drake, Justin (5 December 2019). "Pragmatic signature aggregation with BLS". ethresear.ch/. Eth research. Retrieved 8 January 2021.

[13] "Chain-key signatures | Internet Computer". internetcomputer.org. Retrieved 2024-08-16.

[14] "SKALE Documentation :: SKALE Network Documentation". docs.skale.network. Retrieved 2024-08-16.

[15] "2.1 Cryptography". drand. Retrieved 2024-11-18.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]