Abstract. Wireless Sensor Networks are increasingly being used for data monitoring in commercial, industrial, and military applications. Security is of great concern from many different viewpoints: ensuring that sensitive data does not fall into wrong hands; ensuring that the received data has not been doctored; and ensuring that the network is resilient to denial of service attacks. We study the fundamental problem of Secure Neighbor Discovery problem, which is critical to protecting the network against a number of different forms of attacks. Sensor networks, deployed in hazardous environment, are exposed to a variety of attacks like eavesdropping, message tampering, selective forwarding, wormhole and sybil attacks. Attacks against the data traffc can be addressed using cryptographic techniques. We frst present an effcient and scalable key-distribution protocol which is completely secure in the absence of colluding malicious nodes. Secure neighbor discovery can help to defend against a majority of the attacks against control traffc. We consider a static network and propose a secure one-hop neighbor discovery protocol. We show by analysis that this protocol effectively prevents two non-neighboring nodes from becoming neighbors even when both the nodes have been compromised by the adversary. We then extend this protocol so that it works even when nodes are incrementally deployed in the network. We also brie y study how this protocol could be modifed for mobile sensor networks. Finally, we compare our protocol with existing neighbor discovery protocols and analyze the advantages and disadvantages of using these protocols.

Date of this Version