Navigating in Webs of Trust: Finding Short Trust Chains in Unstructured Networks without Global Knowledge

Authentication of participants is fundamental for secure communication systems. Many traditional systems rely on central components (like certification authorities). These have to be powerful and well-protected, making them expensive, and require trust in a central authority. Conventional decentralized solutions based on local trust between participants only (like PGP) are cheaper but either must be supported by central components, or they are prone to e.g. Sybil attacks. We present a decentralized solution without any trusted central components for finding paths of trust between arbitrary participants in an unstructured network: In an initialization phase a hierarchical overlay structure is constructed, providing each participant with certificate chains to predefined reference nodes. These certificate chains can be used later to find short trust chains between nodes. Monte-Carlo simulations clearly demonstrate the feasibility and efficiency of our approach for social networks. Further features like merging of networks, limited trust relationships between participants and revocation of trust can be integrated easily.