Libert et al. develop a fully distributed, non-interactive, adaptively secure threshold signature scheme with scalable share size.
A threshold cryptosystem enhances the security and availability of public-key schemes by dividing a private key into n shares such that a set of at least t+1 shares is needed to produce a valid private key. If the shares are distributed among n servers, any subset of t+1 servers can produce a digital signature when authorized. Currently, most practical threshold signature schemes have several drawbacks: “they have [only] been analyzed in a ... model where the set of corrupted servers is fixed at the beginning”; they require interaction among the servers; they are not fully distributed by assuming a trusted dealer in the key generation phase; and they require substantial storage.
The authors develop a system that significantly improves on prior solutions by eliminating these drawbacks. In their system, no trusted dealer who assembles the shares is required; hence their solution is fully distributed. According to the paper, “servers can compute their partial signatures without communication with other servers.” The system can tolerate an adversary that can corrupt servers dynamically; private shares are of constant size, independent of the number of servers; and only certain solutions incur O(n) storage cost at the servers. Finally and maybe most importantly, their solution does not require erasure.