Mahdi Rahimi
Today's scale of online activity exposes users to significant privacy risks. A widely adopted safeguard is encryption, which conceals the content of shared data from network intermediaries. However, content protection alone is insufficient. In particular, every digital exchange also generates metadata—such as the sender and recipient of the transmitted data, timestamps, traffic volume, and other contextual information—which constitutes a substantial source of privacy leakage. When collected and analyzed, this metadata can reveal online behavior, social network structures, and other sensitive patterns. To mitigate these risks, anonymous communication systems have been developed under various design paradigms. Among such systems, mix networks (mixnets) remain one of the strongest approaches for limiting metadata leakage. A mixnet operates as an overlay network in which users do not send data directly to recipients. Instead, traffic is routed through a sequence of intermediaries called mixnodes. Each mixnode applies a cryptographic transformation to incoming packets, mixes them with traffic from other users by reordering them, and subsequently forwards them to the next hop. Through layered encryption and probabilistic mixing at every hop, communication metadata becomes unlinkable from its origin—potentially preventing privacy breaches even against a global passive network adversary capable of observing all Internet communication exchanges. Despite their strong privacy guarantees, current mixnet designs face both practical and security limitations. Firstly, mixnets incur substantial latency overhead. In particular, each user communication packet must traverse multiple intermediaries rather than being delivered directly to its recipient, and every mixnode introduces additional delay when forwarding packets due to mixing operations. As a result, mixnets remain primarily suitable for latency-tolerant services such as email, file sharing, or cryptocurrency transactions, while their applicability to latency-sensitive applications—such as web browsing, instant messaging, or live streaming—remains limited. This limitation discourages broader adoption and ultimately reduces the size of the user base, thereby weakening the effective privacy guarantees provided by the system. Accordingly, one major objective of this thesis is to address these latency challenges by introducing protocols for mixnet node arrangement and selection of intermediate mixnodes, together with novel anonymity metrics for rigorous evaluation. At a high level, we design mechanisms that (i) arrange the mixnet such that the probability of forming communication paths composed of latency-proximate mixnodes increases; (ii) enable routing algorithms that prioritize such low-latency paths; and (iii) implement load-balancing mechanisms to ensure that mixnodes handle approximately equal traffic volumes. Through comprehensive simulations and empirical assessments, we show that one of our proposed approaches reduces mixnet latency by up to 9X compared to a baseline configuration, while incurring an anonymity loss of no more than 10%. Secondly, a distinct practical security challenge in mixnets concerns long-term exposure to compromised mixnodes. In typical mixnet deployments, each communication packet is assigned an independently and uniformly random path composed of intermediate mixnodes. While this approach increases mixing diversity and limits correlations between packets within a session—thereby reducing the advantage of a global network adversary—it simultaneously increases the probability that, over time, at least one packet traverses a path consisting entirely of adversarial mixnodes. Once such an event occurs, an adversary controlling those nodes can deanonymize the corresponding communication session by revealing the relationship between source and destination. Specifically, our analysis indicates that compromising only 10-15% of mixnodes may suffice to achieve full deanonymization once the exchanged data volume exceeds approximately 4-30 MB (e.g., sharing an image online) under current mixnet deployments. To address this vulnerability, the second objective of this thesis is to introduce a set of path selection techniques that balance resistance to global adversaries with long-term resilience against compromised mixnodes. Through theoretical analysis, empirical measurements, and extensive simulations, we demonstrate that our proposals reduce vulnerability to compromised mixnodes by up to 85%, while introducing only a marginal increase in the advantage of a global adversary. Collectively, these results show that our approaches enhance both the practicality and the security of mixnets for today's Internet services.