ABSTRACT:

As decentralized computing scenarios get ever more popular, unstructured topologies are natural candidates to consider running mix networks upon. A mix is a special type of message relay service that minimizes the correlation between input and output messages; a mix network topology is simply the graph representing mixes and their interconnections. Most mix-networks thus far rely on structured graph topologies, since they are provably optimal. However, such networks while optimal in theory can have robustness problems in the real world where some mix operators are threatened and harassed to shutdown their mixes. We therefore explore whether networks of social trust might be used in designing better mix-networks. In this talk, I shall attempt to present an analysis of mix-network design based on unstructured topologies such as those found in social networks. We will first consider a number of theoretical models such as scale-free random and Klienberg-Watts-Strogatz topologies before moving on to a real-world example comprising 4 million nodes from an online friendship network. We will explore the efficiency and traffic analysis resistance properties in each of these cases and compare them to the performance of mix-networks on structured graph topologies.