Small Worlds in Security Systems: an Analysis of the PGP Certificate Graph

We propose a new approach to securing computer networks. With this approach, we achieve security in a fully self-organized manner; by this we mean that to secure a computer network, a security system does not require any kind of certification authority or centralized server, even for the initialization phase. In our work, we were inspired by PGP because its functionality relies solely on the acquaintances between users. We show that the small-world phenomenon naturally emerges in the PGP system as a consequence of the self-organization of the users. We show this by studying the PGP certificate graph properties and by quantifying its small-world characteristics. We argue that the certificate graphs of the self-organized security systems will exhibit a similar small-world phenomenon, and we provide an efficient way to construct these certificate graphs. The results of the PGP certificate graph analysis and graph modeling can be used to build new self-organized security systems and to test the performance of the existing systems. In this work, we refer to such an example. The motivation for our work comes from the problem of securing fully self-organized mobile ad hoc networks.