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.

Mix networks (mixnets) safeguard client anonymity by forwarding traffic through multiple intermediary nodes (mixnodes), which reorder and delay messages to obscure communication patterns against a global passive adversary capable of monitoring all network transmissions.The anonymity provided by mixnets is usually assessed with a discrete-event simulator, gauging a target message's indistinguishability among output messages.While useful for comparative analysis, this approach only approximates the mixnet's anonymity potential.Hence, this paper sheds light on the necessity of considering the client (originator of messages) itself to gauge anonymity accurately.We further provide an algorithm (simulator) to simulate client anonymity for Loopix mixnets.We conduct experiments to optimize general Loopix mixnet parameters, considering both message and client anonymity.Our findings indicate that message anonymity often provides an upper bound and can yield misleading results for mixnet optimization, underscoring the importance of client anonymity.Additionally, we explore scenarios where client anonymity is significantly compromised due to an insufficient number of clients.To address these cases, we propose a multimixing strategy that enhances client anonymity by effectively merging varied traffic types with different mixing characteristics.

Mix networks (mixnets) enhance anonymity at the cost of increased end-to-end latency, deterring clients from adopting mixnets for web browsing or instant messaging. This often leads clients to seek alternative anonymous communication systems, potentially compromising on anonymity levels. Addressing this, LARMix (NDSS 2024) introduced a strategic message routing aimed at minimizing link latency within mixnets. However, LARMix's proposal does not cover reducing link latency from clients to the mixnet. Filling this gap, CLAM presents innovative methodologies for efficient message forwarding from clients to mixnets. Our analysis reveals that clients using CLAM can reduce link latency to the mixnet by up to 90% without significantly burdening the network. Moreover, our results indicate that optimizing client routing in mixnets does not substantially increase the risk of message deanonymization, even with adversaries compromising up to 20% of nodes in the mixnet.

Mix networks (mixnets) offer robust anonymity even against adversaries monitoring all network links; however, they impose high latency on communications. To address this, recent research has explored strategic low-latency routing within mixnets. While these strategies appear to reduce latency, their impact on mixnet anonymity has not been carefully assessed, raising concerns about potential deanonymization of clients. Tackling this challenge, this paper first quantifies the anonymity loss associated with low-latency routing techniques in mixnets. Building on these insights, second, we introduce a novel lowlatency routing method that maintains mixnet anonymity while achieving significant latency reductions compared to the state-of-the-art solution LARMix (NDSS, 2024). Our approach also ensures a more balanced load distribution among mixnet nodes. Moreover, under adversarial conditions where parts of the mixnet are compromised, our method does not confer significant advantages to the adversary, unlike LARMix. Thus, our proposal emerges as the optimal choice for low-latency routing in mixnets.