Robust RSA distributed signatures for large-scale long-lived ad hoc networks

Ad hoc environments are subject to tight security and architectural constraints, which call for distributed, adaptive, robust and efficient solutions. In this paper we propose a distributed signature protocol for large-scale long-lived ad hoc networks. The proposed protocol is based on RSA and a new ( t , t ) -secret sharing scheme. The nodes of the network are uniformly partitioned into t classes, and the nodes belonging to the same class are provided with the same share. Any t nodes, belonging to different classes, can collectively issue a signature, without any interaction. The scheme is at least as secure as any ( t , n ) -threshold scheme, i.e., an adversary can neither forge a signature nor disrupt the computation, unless it has compromised at least t nodes, belonging to different classes. Moreover, an attempt to disrupt the distributed service, by providing a fake signature share, would reveal the cheating node. Further, it is possible to easily increase the level of security, by shifting from a ( t , t ) to a ( t + k , t + k ) scheme, for a reasonable choice of parameter k, involving just a fraction of the nodes, so that the scheme is adaptive to the level of threat that the ad hoc network is subject to.

Finally, the distributed signature protocol is efficient: the number of messages sent and received for generating a signature, as well as to increase the level of security, is small and both computations and memory required are small as well.