hinTS: Threshold Signatures with Silent Setup

We propose hinTS — a new threshold signature scheme built on top of the widely used BLS signatures. Our scheme enjoys the following attractive features:A silent setup process where the joint public key of the parties is computed as a deterministic function of their locally computed public keys.Support for dynamic choice of thresholds and signers, after the silent setup, without further interaction.Support for general access policies; in particular, native support for weighted thresholds with zero additional overhead over standard threshold setting.Strong security guarantees, including proactive security and forward security.We prove the security of hinTS in the algebraic group model, and also provide an open-source implementation. Our scheme outperforms all prior proposals that avoid distributed key generation in terms of aggregation time, signature size, and verification time (as well as other qualitative measures). As an example, the aggregation time in hinTS for 1000 signers is under 0.5 seconds, while both signing and verification are constant time algorithms, taking 1 ms and 17.5 ms, respectively.The key technical contribution of our work involves the design of special-purpose succinct proofs to efficiently prove the well-formedness of aggregated public keys. Our solution uses public "hints" released by the signers as part of their public keys (hence the name hinTS).