DP-Mix: Differentially Private Routing in Mix Networks
Mahdi Rahimi · 2025
Mixnets, as overlay networks, ensure anonymity for messages by forwarding them through intermediary nodes that obscure their traffic patterns from network-level adversaries. Nonetheless, the selection of intermediaries is traditionally performed uniformly at random, resulting in optimal routes being chosen no more frequently than suboptimal ones. This often causes messages to traverse inefficient paths that degrade performance or weaken security. While there have been proposals to improve route selection in mixnets, they are limited to latency reduction and rely on heuristic strategies that lack formal anonymity guarantees. To bridge this gap, we develop a framework for differ-entially private routing in mixnets aimed at general-purpose optimization. In this framework, each candidate route is as-signed an optimality score, and routes are then selected to favor high-scoring paths while preserving anonymity under a pure-ε differential privacy guarantee. We instantiate this model for optimizing path security, enhancing reliability, and minimizing communication latency. Additionally, we introduce a gradient-based algorithm applied post hoc to the route selection process-without weakening privacy guarantees-to prevent the over-selection of particular nodes, which could otherwise lead to security vulnerabilities or network congestion. Through analytical evaluation and simulation over data from deployed Nym mixnets, we demonstrate that DP-Mix consistently achieves high optimality scores across all instantiations while preserving a strong level of anonymity. In particular, for latency optimization, our method outperforms state-of-the-art solutions, achieving up to a 8× improvement in the latency-anonymity trade-off.