Provable Mixing Properties of Parallel Mixnets Revisited

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.

Authors

Publication Details

Journal
arXiv (Cornell University)
Published
2026-11-17
DOI
https://doi.org/10.48550/arxiv.2611.22732
Primary Topic
Internet Traffic Analysis and Secure E-voting
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Provable Mixing Properties of Parallel Mixnets Revisited

Peter Druschel, Pierfrancesco Ingo, Deepak Garg
arXiv (Cornell University)
Internet Traffic Analysis and Secure E-voting
preprint

Provable Mixing Properties of Parallel Mixnets Revisited

Peter Druschel, Pierfrancesco Ingo, Deepak Garg
preprint en

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.

arXiv (Cornell University)
Internet Traffic Analysis and Secure E-voting
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon