VISO: A SCC-based Key Establishment Scheme for Mobile Ad Hoc Networks

H. You, P. Zheng, and M. Lu (USA)


key establishment scheme, mobile ad hoc network, network security


In a mobile ad hoc network where a trusted authority is not available, how to provide distributed and efficient security service becomes a challenging problem. In this paper, we propose a VISO (VIrtual Security Overlay) scheme that can provide distributed public-key search service with high probability and efficient usage of local storage, which makes our scheme highly scalable and very suitable for large mobile ad hoc networks where secured communication needs to be built up between any pair of users. In our scheme, each user chooses its public key/secret key pair, and issues certificates to other users by itself. A simple yet effective distributed scheme is proposed to identify the largest strong-connected component (SCC) of a certificate graph that maps all public keys and certificates of the network. By utilizing the property of a SCC, each user selects only a few public keys and certificates to store locally, and a pair of users can discover the authentic public key of each other with very high probability by combining their stored information. Comparing with existing schemes of similar architecture, users store much fewer (<1/10) selected public keys and certificates while providing public-key search service with a >99% probability in our scheme. In addition, our scheme can provide guaranteed public-key search service if the whole certificate graph is a SCC.

Important Links:

Go Back