Fully Distributed Non-Interactive Adaptively-Secure Threshold Signature Scheme with Short Shares: Efficiency Considerations and Implementation

Joint work with: Benoı̂t Libert, Marc Joye, Moti Yung.

Partial Abstract. We present a practical fully distributed non-interactive scheme — where the servers can compute their partial signatures without communication with other servers —with adaptive security (i.e., the adversary corrupts servers dynamically based on its full view of the history of the system). Our scheme is very efficient in terms of computation, communication, and scalable storage (with private key shares of size O(1), where certain solutions incur O(n) storage costs at each server). Unlike other adaptively secure schemes, our scheme is erasure-free. Of particular interest is the fact that Pedersen’s traditional distributed key generation (DKG) protocol can be safely employed in the initial key generation phase when the system is set up although it is well-known not to ensure uniformly distributed public keys. An advantage of this is that this protocol only takes one round in the absence of faulty player.

(Click the above image to see video on Youtube)