A Deep Dive Into the Threshold BLS Signature Scheme

Abstract. Threshold signature schemes protect the signing key by sharing it among a group of signers so that an adversary must corrupt a threshold number of signers to be able to forge signatures. The increasing demand for decentralized applications has resulted in large-scale adoption of threshold signature schemes. A popular choice of threshold signature is the BLS signature, introduced by Boldyreva building on the work of Boneh–Lynn–Shacham [BLS01]. Boldyreva’s BLS threshold signature scheme is popular because its verification is identical to a standard non-threshold BLS signature, its signing process is non-interactive, the signatures are unique and small (a single elliptic curve group element), and the scheme is very efficient in terms of both computation and communication. These properties have resulted in practical adoptions of Boldyreva’s BLS threshold signature for applications in the decentralized setting. In this talk, I will take a deep dive into the design and implementation of Boldyreva’s Threshold BLS signature scheme. Specifically, I will talk about Shamir's secret sharing scheme, the original BLS signature scheme, and how we can thresholdize it. Finally, I will also provide a walk-through a prototype implementation of the scheme.

Based on work performed while at UIUC.

Suggested readings: 

• How to share a secret (1979)
• Short Signatures from the Weil Pairing (2001)
• Threshold signatures, multisignatures ... (2003)
• T-BLS implementation exercise (2022)

[Slides]