A Certification Authority (CA) can be used to certify keys and build a public-key infrastructure (PKI) when all users trust the same CA. A decentralized PKI trades off absolute assurance on keys for independence from central control and improved scalability and robustness. The PGP ``web of trust'' model has been suggested as a decentralized certification system, and has been used with great success for secure email. Although the PGP web of trust model allows anyone to issue certificates which can be used to form certificate chains, the discovery and construction of certificate chains relies on centralized keyservers to store certificates and respond to queries.

In this paper, we design and implement KeyChains, a peer-to-peer system which incorporates a novel lookup mechanism specifically tailored to the task of generating and retrieving certificate chains in completely unstructured networks. By layering our system on top of the web of trust model, we thus obtain the first PKI which is truly decentralized in all respects. Our analysis and simulations show that the resulting system is both efficient and secure.