Paper 2022/534

On the Adaptive Security of the Threshold BLS Signature Scheme

Renas Bacho, CISPA Helmholtz Center for Information Security
Julian Loss, CISPA Helmholtz Center for Information Security

Threshold signatures are a crucial tool for many distributed protocols. As shown by Cachin, Kursawe, and Shoup (PODC '00), schemes with unique signatures are of particular importance, as they allow to implement distributed coin flipping very efficiently and without any timing assumptions. This makes them an ideal building block for (inherently randomized) asynchronous consensus protocols. The threshold BLS signature of Boldyreva (PKC '03) is both unique and very compact, but unfortunately lacks a security proof against adaptive adversaries. Thus, current consensus protocols either rely on less efficient alternatives or are not adaptively secure. In this work, we revisit the security of the threshold BLS signature by showing the following results, assuming $t$ adaptive corruptions: - We give a modular security proof that follows a two-step approach: 1) We introduce a new security notion for distributed key generation protocols (DKG). We show that it is satisfied by several protocols that previously only had a static security proof. 2) Assuming any DKG protocol with this property, we then prove unforgeability of the threshold BLS scheme. Our reductions are tight and can be used to substantiate real-world parameter choices. - To justify our use of strong assumptions such as the algebraic group model (AGM) and the hardness of one-more-discrete logarithm (OMDL), we prove two impossibility results: 1) Without the AGM, we rule out a natural class of tight security reductions from $(t+1)$-OMDL. 2) Even in the AGM, a strong interactive assumption is required in order to prove the scheme secure.

Available format(s)
Publication info
Threshold Signatures BLS Signatures Algebraic Group Model
Contact author(s)
renas bacho @ cispa de
lossjulian @ gmail com
2022-11-22: last of 8 revisions
2022-05-10: received
See all versions
Short URL
Creative Commons Attribution


      author = {Renas Bacho and Julian Loss},
      title = {On the Adaptive Security of the Threshold BLS Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2022/534},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.