Affiliations: [a] Dipartimento di Informatica of the Università di Roma “La Sapienza”, Italy. E-mail: [email protected], [email protected] | [b] Dipartimento di Matematica of Università di Roma Tre, Italy. E-mail: [email protected]
Correspondence:
[*]
Corresponding author. All the authors have been partially funded by the WEB-MINDS project, supported by the Italian MIUR under the FIRB program. Roberto Di Pietro is also partially supported by the CNR-ISTI, Pisa, in the framework of the “SatNEx-II” NoE project (contract N. 27393).
Abstract: 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.
Keywords: Threshold cryptosystem, signature scheme, secret sharing, peer-to-peer network, ad hoc networks, wireless network, ubiquitous service
