cispa_all_3845.pdf (711.5 kB)

On the Adaptive Security of the Threshold BLS Signature Scheme

Download (711.5 kB)
conference contribution
posted on 2023-11-29, 18:26 authored by Renas BachoRenas Bacho, Julian LossJulian Loss
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 an impossibility result: Even in the AGM, a strong interactive assumption is required in order to prove the scheme secure.


Preferred Citation

Renas Bacho and Julian Loss. On the Adaptive Security of the Threshold BLS Signature Scheme. In: ACM Conference on Computer and Communications Security (CCS). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

ACM Conference on Computer and Communications Security (CCS)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_3845, title = "On the Adaptive Security of the Threshold BLS Signature Scheme", author = "Bacho, Renas and Loss, Julian", booktitle="{ACM Conference on Computer and Communications Security (CCS)}", year="2022", }

Usage metrics


    No categories selected


    Ref. manager