Security is an important consideration for many applications of ad-hoc networks. While security aspects of the routing layer have been addressed extensively, there is relatively lesser work on establishing a viable public key infrastructure, which is the basis for most security protocols. We present a distributed algorithm for validating the association between the network identifier of a host and its public key without relying on a priori shared secrets or a trusted certification authority.