CS Paper Radar

Provable Mixing Properties of Parallel Mixnets Revisited

Pierfrancesco Ingo, Peter Druschel, Deepak Garg

cs.CR ·submitted 2026-11-17 13:02 UTC · v1

Abstract

A mix-network (mixnet) is a routing network that breaks source-to-destination message trackability by indistinguishably mixing the routes of concurrently transmitted messages, thus providing anonymity to senders, receivers and sender-receiver pairs. Given their potential use in high-stakes scenarios like protecting whistleblowers, one would like to prove formally that sender anonymity holds in a mixnet, even against strong adversaries that can compromise subsets of mixnet servers. However, existing work on anonymity in mixnets is either limited to linear mixnets (which do not scale horizontally), relies on special provisions such as additional noise or chaff messages, or is empirical -- typically based on entropy, which does not provide strong guarantees if the adversary has auxiliary information. In this paper, we present a new analysis of parallel mixnets which scale horizontally, showing that these networks can provide strong indistinguishability for messages even without additional noise messages. Our analysis works by bounding the statistical variance of the adversary's posterior likelihood of where a message of interest is at a given point in time. Using concentration bounds on this distribution, we show that parallel mixnets satisfy $(\varepsilon, δ)$-differential indistinguishability for messages routed through the mixnet (similar to $(\varepsilon, δ)$-differential privacy) with very small failure probabilities $δ$ and small privacy parameters $\varepsilon$ under reasonable operating conditions. Our model also enables an examination of the quantitative trade-off between anonymity, latency and per-router bandwidth in parallel mixnets.

Comment
16 pages, 3 figures, 2 pages of appendix

Closest papers

Nearest neighbours by meaning across the whole index.

Hidden Services Protocol for Mixnets

cs.CR ·2026-09-01 ·Nicolas Constantinides, Mahdi Rahimi, Stavros Nonis
code/data similarity 0.67
Abstract

Mix networks (mixnets) provide network-level privacy by routing each communication packet through a sequence of intermediaries, called mixnodes, that randomly delay and cryptographically transform packets before forwarding them, making it difficult for observers to link mixnet entries to exits. While this mechanism protects sender privacy from both external adversaries and the receiver, existing mixnets lack a secure and practical protocol that simultaneously protects receiver (destination) privacy, particularly from the sender. We close this gap. We introduce the first practical and secure hidden-service protocol for mixnets, providing receiver privacy alongside sender anonymity. Our design builds on Single-Use Reply Blocks (SURBs), which enable anonymous replies without revealing the receiver's address. We show, however, that existing approaches to using SURBs expose two practical attacks that can compromise sender or receiver anonymity when the opposing party controls only a single mixnode. We develop defenses against both vulnerabilities. Building on these defenses, we introduce NymHS, a secure and practical hidden-service protocol for mixnets that supports anonymous service discovery, authenticated bidirectional sessions, and asynchronous SURB replenishment. We implement NymHS on the open-source Nym codebase and evaluate its practicality through web-browsing experiments across 118 websites, measuring each of the 27 configurations three times (9,558 page loads). Our results demonstrate that hidden services can be deployed efficiently over mixnets. In particular, increasing the Sphinx payload from 2 KiB to 10 KiB reduces mean page-load latency by approximately 5.2x and decreases communication overhead from 21.7% to 4.3% relative to the current Nym baseline.

0.42

On the Effectiveness of NetFlow-Based Deanonymization of Tor Onion Services (Extended Version)

cs.CR ·2026-10-10 ·Jinseo Lee, Jongkook Han, Yixin Sun, Min Suk Kang
top venue similarity 0.62
Abstract · To appear at IEEE Symposium on Security and Privacy 2027

In the context of Tor, deanonymization attacks via traffic correlation have long been studied for both clients and onion services. Complementing prior investigations that utilize fine-grained flow metadata such as packet sizes and timings, we study a relatively less explored yet easier-to-obtain adversarial capability: deanonymization using only coarse NetFlow-style telemetry, such as one-minute, 1-out-of-1,000 sampled packet counts. We first revisit active NetFlow-based traffic analysis attacks against Tor onion services and show, through large-scale experiments with live Tor data, that coarse telemetry is sufficient to deanonymize a targeted onion service when the adversary can induce discernible traffic patterns through controlled downloads. We then introduce a stronger active attack based on controlled introduction requests, which removes application-specific assumptions and gives adversaries more flexibility while achieving comparable success rates. Finally, we present a passive deanonymization attack that sends zero traffic to target onion services. The attack exploits Tor's puzzle-based DoS defense as a side channel: public puzzle difficulty reveals service-load changes that can be semantically matched against NetFlow traces. Our findings show that coarse network telemetry poses a practical deanonymization threat to onion services today and call for proactive mitigations and a redesign of the globally visible defense signals that may leak service-load information.

0.24

DP-VOXLET: Provable Speaker Anonymization for Disentangled Speech Representations

cs.CR ·2026-08-31 ·Ivoline Ngong, Jack D'Iorio, Hailey Schoppe, Christopher Liberatore, Nichole Schimanski +2 more
top venuetheory similarity 0.58
Abstract

Systems for speaker anonymization obfuscate the speaker of an utterance, while maintaining its original semantic contents and prosody. Recent solutions for speaker anonymization rely on learned representations that disentangle an utterance into semantic contents and speaker properties. To anonymize an utterance, these systems replace the speaker properties while leaving the semantic contents unchanged---an approach that can produce strong results on empirical measures of privacy. In this work, we introduce speaker differential privacy, a formal definition of speaker anonymization based on the framework of differential privacy, and a mechanism for speaker anonymization that provably satisfies the definition. In contrast to prior heuristic-based anonymization systems, our approach enables a provable lower bound on re-identification success rate (e.g. equal error rate) for any possible adversary. We implement our approach in a framework that is compatible with existing disentangled representations. Compared to the prior work on differential privacy for speaker anonymization, our approach achieves significantly higher utility.

0.38

Closing the Loop: Bidirectional Fully Encrypted Protocols

cs.CR ·2026-09-15 ·Baigang Chen, Nicholas Hopper
similarity 0.58
Abstract

Fully encrypted protocols (FEPs) provide encrypted channels that make all protocol-generated bytes computationally indistinguishable from uniform random strings. Several previous works have explored security definitions and constructions of unidirectional FEPs: protocols in which one party acts only as a sender, and the other acts only as a receiver. However, most applications require two-way information exchange, and a network adversary can observe communication in both directions and their shared lifetime. Because the semantics of bidirectional channels involve more complex shared state, it is possible that the ``naïve'' composition of two unidirectional channels can result in a two-way protocol that can be detected based on dependencies between the two directions, such as traffic imbalance, channel closure, failures, or connection tear-down. To address this issue, we introduce new formal security definitions for bidirectional FEPs that capture exact shaping, delivery, protocol-state integrity, private half-close, and cross-direction isolation, while revealing a public ``sending schedule'' and ``closing epoch'' that may be randomized. We show that the trivial composition fails to meet these definitions, leading to practical detection attacks. We then construct provably secure bidirectional FEPs (BiFEPs) for both the datastream and datagram settings. For datastream, we combine two direction-separated FEPs with a ``wrapper'' layer that prevents detection based on the mismatch between uni- and bi-directional connection states. For datagram, we add encrypted DATA/FIN/ACK with replay protection and loss-tolerant close. We validate the design through a Rust implementation and show that none of the surveyed deployed protocols provides the full set of BiFEP security properties.

0.16

Attacking P2P Networks: Liveness Attacks on the GossipSub and DOG Gossip Protocols

cs.CR ·2026-11-02 ·Jiaheng Li, Anton Paramonov, Yann Vonlanthen
similarity 0.57
Abstract

Peer-to-peer (P2P) networks form the communication layer of large decentralized systems such as Ethereum, and the correctness of higher-level protocols depends on the gossip layer delivering messages to honest nodes. We study the robustness of two gossip protocols against adversaries whose only goal is to violate liveness, that is, to prevent honest nodes from receiving fresh messages, without forging, altering, or invalidating any message. For GossipSub, the publish-subscribe protocol used by Ethereum, we show that an adversary operating a constant number of geographically distributed nodes with a fixed latency advantage can take over the ``First Message Deliveries'' peer-scoring term and separate a constant fraction of nodes from the honest mesh. We analyze the attack under a geographical model, address the random-peer and outbound-connection mechanisms, and show that the separation can be maintained under realistic churn. For DOG, a transaction-dissemination protocol designed for CometBFT, we first give simple counterexamples in which route filtering disconnects the dissemination graph even without failures or Byzantine participants, and then present a practical attack that uses only a single physical node with a constant number of identities and legitimate actions to disable every forwarding route, separating the full network while allowing only direct publisher-to-neighbor delivery. We verify the attack in a simulated network and analyze its cost, assumptions, and possible mitigations.

0.11

Privacy, Robustness, and Fairness Trade-offs in Federated Intrusion Detection: Geometric Indistinguishability at the Aggregation Interface

cs.CR cs.AIcs.LG ·2026-09-03 ·Adrita Rahman Tory, ABM Shawkat Ali, Md Abu Layek, Khondokar Fida Hasan
hot direction similarity 0.57
Abstract · 16 pages

Federated learning enables privacy-conscious collaboration for network intrusion detection without centralizing sensitive traffic data, yet its deployment in operational environments must simultaneously satisfy three competing requirements: formal differential privacy guaranties, tolerance to Byzantine-adversarial participants, and reliable detection coverage across severely imbalanced attack categories. Existing literature treats these properties as independently composable, an assumption that this paper challenges both theoretically and empirically. In this paper, we study how these requirements interact in class-imbalanced federated NIDS and introduce geometric indistinguishability as a conceptual lens for a regime in which privacy-induced dispersion in client updates can make minority-class signals harder for robust aggregation to preserve. Using UNSW-NB15 as a case study, we evaluate DP-SGD combined with coordinate-wise median under label-flip and model-poisoning attacks, with threat coverage assessed across attack categories. Our results provide initial evidence that the joint use of privacy noise and robust aggregation can disproportionately degrade detection of rare attacks relative to majority classes. We also show that part of the observed collapse under strong privacy can arise from training miscalibration, while a residual performance floor may remain for ultra-rare categories even after epsilon-dependent tuning. These findings motivate studying privacy, robustness, and rare-attack coverage jointly rather than as independently composable properties, and suggest that aggregation-aware modeling and sample-aware evaluation are promising directions for trustworthy federated NIDS.

0.27

The Cost of Stability: Deanonymizing Onion Services Long-Lived Introduction Circuits

cs.CR ·2026-09-27 ·Nicolas Constantinides, Mahdi Rahimi
similarity 0.57
Abstract

Tor is a widely used anonymity network that provides network privacy by routing client communications through a sequence of relays to their destinations. An adversary observing a single Tor relay cannot readily link clients to their destinations, as doing so requires identifying the other relays along the client circuit. Identifying these relays from traffic observed at the monitored relay alone is challenging: each relay carries traffic for many circuits simultaneously, and client circuits typically last only about 10 min, limiting observations of a given circuit. In contrast, Tor onion services use introduction circuits that remain fixed for 18 to 24 h. We develop an intersection attack that exploits this design, allowing an adaptive adversary observing one Tor relay at a time to identify the network location of an onion service. We evaluate the attack on the live Tor network against a self-operated onion service carrying genuine third-party traffic. Across nine end-to-end experiments, the attack reconstructs the complete Tor circuit in every run, with an estimated median time of 2.2 h. To mitigate this attack, we propose a mechanism that periodically rebuilds internal introduction circuits to limit evidence accumulation without changing publicly advertised information.

0.21

One-Shot Information Hiding and Compound Wiretap Channels

cs.IT ·2026-09-18 ·Yanxiao Liu, Cheuk Ting Li
similarity 0.56
Abstract

In recent years, due to the growing reliance on large amounts of data that are communicated, analyzed, and utilized, which inherently contain sensitive and personal information, secrecy and privacy in communication have become increasingly important. We present nonasymptotic information-theoretic analyses of two fundamental secrecy problems under channel uncertainties: the information hiding problem and the compound wiretap channel. The former admits a game-theoretic formulation, where one party (an information hider and a decoder) seeks to embed secret messages into a host signal for later reconstruction, while the opposing party (an attacker) attempts to remove or degrade the embedded information. The latter generalizes Wyner's wiretap channel by allowing multiple potential channel states. The information hiding problem concerns active attacks during data transmission, while the compound wiretap channel addresses passive eavesdropping and information leakage. The two problems, both of which consider channels with uncertainties, can be studied under a unified framework by utilizing a covering argument and the Poisson matching lemma by Li and Anantharam. We derive novel one-shot achievability results for both problems that are applicable to any source distribution and any class of channels (not necessarily memoryless or ergodic), and that apply to both discrete and continuous cases. We also show that existing asymptotic results on both problems can be recovered by applying our results to discrete memoryless channels.

0.17