When IPv6 Neighbor and Router Discovery functions were defined, it was assumed that the local link would consist of mutually trusting nodes. However, the recent developments in public wireless networks, such as WLANs, have radically changed the situation. The nodes on a local link cannot necessarily trust each other any more, but they must become mutually suspicious even when the nodes have completed an authentication exchange with the network. This creates a number of operational difficulties and new security threats. In this paper we provide a taxonomy for the IPv6 Neighbor and Router Discovery threats, describe two new cryptographic methods, Cryptographically Generated Addresses (CGA) and Address Based Keys (ABK), and discuss how these new methods can be used to secure the Neighbor and Router discovery mechanisms.