Threshold cryptography in mobile ad hoc networks under minimal topology and setup assumptions

Mobile Ad Hoc Networks (MANET), due to their lack of physical infrastructures or centralized online authorities, pose a number of security challenges to a protocol designer. In particular, several typical application scenarios demand the design of protocols that cannot base their security on the existence of trusted parties or setup information, but rather need to leverage uniquely on assumptions limiting the corrupting power of the adversaries. This naturally defines security design and analysis paradigms similar to those of the threshold cryptography area, where it is typically assumed that an adversary can corrupt up to a limited amount of entities or resources. Therefore a secure realization of primitives from threshold cryptography in MANET promises to be applicable to several MANET protocols. However, directly applying known threshold cryptography solutions for wired network into MANETs faces serious challenges. In particular, we noted a major design difficulty due to the lack of full network connectivity that significantly constrained the network topology assumptions under which a MANET threshold signature scheme can be proved secure. In this paper we formalize, investigate and present a new MANET threshold signature scheme that is secure under significantly improved topology and setup assumptions. Surprisingly, we break through an apparent barrier due to well-known results from the distributed computing area.