pith. sign in

arxiv: 1907.11603 · v1 · pith:MYOTLX7Knew · submitted 2019-07-26 · 💻 cs.PF · cs.IT· math.IT

Anonymity Mixes as (Partial) Assembly Queues: Modeling and Analysis

Mehmet Fatih Aktas , Emina Soljanin This is my paper

Pith reviewed 2026-05-24 15:13 UTC · model grok-4.3

classification 💻 cs.PF cs.ITmath.IT
keywords batch mixesanonymityassembly queuesqueueing modeldelay scalingrandomized mixingtime-to-deanonymize
0
0 comments X

The pith

Batch mixes modeled as assembly queues show delay surging as batch size nears sender count, with randomization improving scaling but cutting anonymity.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces a queueing model that represents batch mix operation as a partial assembly process, where messages must accumulate to a threshold before forwarding to obscure sender-receiver links. Analysis of this model establishes that average message delay increases sharply once the batch size required for mixing approaches the total number of active senders attached to the mix. The authors then define a randomized batching policy and prove that it yields substantially better delay scaling as a function of batch size. This improvement occurs alongside a reduction in the effective anonymity set preserved by the mix. The queueing framework additionally supports direct examination of operational anonymity metrics such as the time required to deanonymize a participant.

Core claim

By casting batch mix behavior as an assembly queue in which service commences only after a sufficient number of messages arrive, the mean delay is shown to grow rapidly as the batch threshold nears the sender population size; a randomized batching rule then produces improved delay asymptotics, although at the expense of smaller anonymity sets.

What carries the argument

Assembly queue model in which batch formation requires multiple arrivals from distinct senders before the mix forwards the collected messages.

If this is right

  • Delay in conventional batch mixes becomes large when the batch size is set close to the number of connected senders.
  • Randomized batch mixing achieves markedly better delay scaling with respect to batch size.
  • The randomized strategy reduces the anonymity set size maintained by the mix.
  • Queueing models enable quantitative study of time-to-deanonymize metrics that reflect practical attacker capabilities.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Mix operators may need to keep batch sizes well below the sender population to avoid latency spikes.
  • The assembly-queue framing could be applied to analyze threshold-based privacy mechanisms beyond mixes.
  • Direct experiments on live anonymity networks could check whether the derived scaling laws hold under measured traffic.

Load-bearing premise

The queueing model with its chosen arrival process and batch service rules accurately captures how real batch mixes behave under the traffic patterns examined.

What would settle it

Measurement of actual end-to-end delays in a deployed batch mix while varying the batch threshold relative to the number of active senders and comparing those values against the model's predicted curves.

Figures

Figures reproduced from arXiv: 1907.11603 by Emina Soljanin, Mehmet Fatih Aktas.

Figure 1
Figure 1. Figure 1: Illustration of a (4, 3) batch mix. As long as there are less than three non-empty queues, messages are blocked (Left). As soon as a message arrival forms a group of three non-empty queues, one message from each is dispatched (Right). analyzing its incurred delay. Sec. IV introduces a randomized batch mixing strategy, and discusses its anonymity and delay properties. Sec. V gives a summary and conclusions.… view at source ↗
Figure 2
Figure 2. Figure 2: (Left, Middle) Average delay in a batch mix with [PITH_FULL_IMAGE:figures/full_fig_p004_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Markov process for (n, 2)-mix. State here denotes the length of the longest queue in the mix; 0 length means the system is empty. immediately moved to HoL. Then according to our earlier assumption, the number of non-empty queues left behind non￾empty by m is distributed as R. Including the next arrival to the tagged queue, say message m+, the next batch formation requires k − R of the n − R empty queues to… view at source ↗
read the original abstract

Anonymity platforms route the traffic over a network of special routers that are known as mixes and implement various traffic disruption techniques to hide the communicating users' identities. Batch mixes in particular anonymize communicating peers by allowing message exchange to take place only after a sufficient number of messages (a batch) accumulate, thus introducing delay. We introduce a queueing model for batch mix and study its delay properties. Our analysis shows that delay of a batch mix grows quickly as the batch size gets close to the number of senders connected to the mix. We then propose a randomized batch mixing strategy and show that it achieves much better delay scaling in terms of the batch size. However, randomization is shown to reduce the anonymity preserving capabilities of the mix. We also observe that queueing models are particularly useful to study anonymity metrics that are more practically relevant such as the time-to-deanonymize metric.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper models batch mixes in anonymity systems as partial assembly queues with Poisson arrivals from a fixed population of N senders. It shows that delay grows rapidly as batch size B approaches N, proposes a randomized batch mixing strategy that improves delay scaling (with an explicit anonymity trade-off), and argues that queueing models are useful for practical metrics such as time-to-deanonymize.

Significance. If the derivations hold, the work supplies a clean queueing-theoretic treatment of delay scaling in batch mixes together with a randomized variant and its anonymity cost. The explicit mapping to assembly queues, use of standard Poisson-arrival analysis, and focus on time-to-deanonymize are concrete strengths that could aid designers of mix networks.

minor comments (3)
  1. [Abstract] The abstract states that delay 'grows quickly' as B approaches N and that randomization yields 'much better delay scaling,' but does not indicate whether these are asymptotic statements, exact closed forms, or numerical observations; a brief qualifier would help readers assess the strength of the claims.
  2. The weakest modeling assumption (that the chosen arrival process and service discipline accurately capture real batch-mix traffic) is invoked when mapping the mix to an assembly queue and deriving the scaling results; a short paragraph discussing sensitivity to this assumption would strengthen the paper.
  3. Notation for the batch size B, sender population N, and the randomization parameter should be introduced once with a clear table or list of symbols to avoid later ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the paper, the recognition of its contributions, and the recommendation of minor revision. No specific major comments appear in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The derivation maps batch mixing to a standard partial assembly queue under Poisson arrivals from fixed N senders and derives delay scaling from the resulting queueing equations as B approaches N. The randomized variant modifies the service discipline with an explicit anonymity metric trade-off. No step reduces by construction to a fitted parameter, self-citation chain, or ansatz smuggled from prior work; the analysis rests on classical queueing results applied to the new model. The provided abstract and skeptic assessment confirm the central claims remain independent of the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The model relies on standard queueing assumptions (Poisson or general arrivals, batch service discipline) rather than new invented entities or fitted constants. No free parameters are introduced beyond the batch size and sender count treated as design variables.

axioms (2)
  • domain assumption Messages arrive according to a stochastic process that can be modeled by standard queueing theory (e.g., independent inter-arrival times).
    Invoked when mapping the mix to an assembly queue and deriving delay growth.
  • domain assumption The batch service rule (forward only after batch size reached) is the dominant source of delay.
    Central to the claim that delay grows quickly near the number of senders.

pith-pipeline@v0.9.0 · 5684 in / 1381 out tokens · 19619 ms · 2026-05-24T15:13:11.392958+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Reliable, deniable, and hidable communication over multipath networks,

    S. Kadhe, S. Jaggi, M. Bakshi, and A. Sprintson, “Reliable, deniable, and hidable communication over multipath networks,” in 2014 IEEE International Symp. on Inform. Theory . IEEE, 2014, pp. 611–615

    work page 2014

  2. [2]

    Hiding information in noise: Fundamental limits of covert wireless communication,

    B. A. Bash, D. Goeckel, D. Towsley, and S. Guha, “Hiding information in noise: Fundamental limits of covert wireless communication,” IEEE Communications Magazine, vol. 53, no. 12, pp. 26–31, 2015

    work page 2015

  3. [3]

    Covert communication over noisy channels: A resolv- ability perspective,

    M. R. Bloch, “Covert communication over noisy channels: A resolv- ability perspective,” IEEE Transactions on Information Theory , vol. 62, no. 5, pp. 2334–2354, 2016

    work page 2016

  4. [4]

    Towards unconditional tor-like anonymity,

    I. Safaka, L. Czap, K. Argyraki, and C. Fragouli, “Towards unconditional tor-like anonymity,” in The 2015 IEEE International Sumposium on Network Coding (NetCod)-Invited Paper , 2015

    work page 2015

  5. [5]

    Networks without user observability - design options,

    A. Pfitzmann and M. Waidner, “Networks without user observability - design options,” in Workshop on the Theory and Application of Cryptographic Techniques. Springer, 1985, pp. 245–253

    work page 1985

  6. [6]

    Untraceable electronic mail, return addresses, and digital pseudonyms,

    D. L. Chaum, “Untraceable electronic mail, return addresses, and digital pseudonyms,” Commun. of the ACM , vol. 24, no. 2, pp. 84–90, 1981

    work page 1981

  7. [7]

    Limits of anonymity in open environments,

    D. Kesdogan, D. Agrawal, and S. Penz, “Limits of anonymity in open environments,” in Information Hiding. Springer, 2002, pp. 53–69

    work page 2002

  8. [8]

    Dummy traffic against long term in- tersection attacks,

    O. Berthold and H. Langos, “Dummy traffic against long term in- tersection attacks,” in International Workshop on Privacy Enhancing Technologies. Springer, 2002, pp. 110–128

    work page 2002

  9. [9]

    Generalising mixes,

    C. Dıaz and A. Serjantov, “Generalising mixes,” in PET. Springer, 2003, pp. 18–31

    work page 2003

  10. [10]

    Challenges in deploy- ing low-latency anonymity (draft),

    R. Dingledine, N. Mathewson, and P. Syverson, “Challenges in deploy- ing low-latency anonymity (draft),” Unpublished Manuscript. http://tor. eff. org/cvs/tor/doc/design-paper/challenges. pdf, 2005

    work page 2005

  11. [11]

    Deploying low-latency anonymity: Design challenges and social factors,

    ——, “Deploying low-latency anonymity: Design challenges and social factors,” IEEE Security & Privacy , 2007

    work page 2007

  12. [12]

    On the effectiveness of traffic analysis against anonymity networks using flow records

    S. Chakravarty, M. V . Barbera, G. Portokalidis, M. Polychronakis, and A. D. Keromytis, “On the effectiveness of traffic analysis against anonymity networks using flow records.” in PAM. Springer, 2014

    work page 2014

  13. [13]

    Sampled traffic analysis by internet- exchange-level adversaries,

    S. Murdoch and P. Zieli ´nski, “Sampled traffic analysis by internet- exchange-level adversaries,” in Privacy Enhancing Technologies . Springer, 2007, pp. 167–183

    work page 2007

  14. [14]

    Assembly-like queues,

    J. M. Harrison, “Assembly-like queues,” Journal of Applied Probability, vol. 10, no. 2, pp. 354–367, 1973

    work page 1973

  15. [15]

    Anonymity, unlinkability, unobservabil- ity, pseudonymity, and identity management,

    A. Pfitzmann and M. Hansen, “Anonymity, unlinkability, unobservabil- ity, pseudonymity, and identity management,” Technical report, 2005

    work page 2005

  16. [16]

    An operational measure of information leakage,

    I. Issa, S. Kamath, and A. B. Wagner, “An operational measure of information leakage,” in Information Science and Systems (CISS), 2016 Annual Conference on . IEEE, 2016, pp. 234–239

    work page 2016

  17. [17]

    Delay anonymity tradeoff in mix networks: Optimal routing,

    O. Javidbakht and P. Venkitasubramaniam, “Delay anonymity tradeoff in mix networks: Optimal routing,” IEEE/ACM Transactions on Network- ing (TON), vol. 25, no. 2, pp. 1162–1175, 2017

    work page 2017

  18. [18]

    Anonymous networking with minimum latency in multihop networks,

    P. Venkitasubramaniam and L. Tong, “Anonymous networking with minimum latency in multihop networks,” in 2008 IEEE Symposium on Security and Privacy (sp 2008) . IEEE, 2008, pp. 18–32

    work page 2008

  19. [19]

    An analysis of the degradation of anonymous protocols

    M. K. Wright, M. Adler, B. N. Levine, and C. Shields, “An analysis of the degradation of anonymous protocols.” in NDSS, 2002, pp. 39–50

    work page 2002

  20. [20]

    An overview of some stochastic stability methods,

    S. Foss and T. Konstantopoulos, “An overview of some stochastic stability methods,” J. of the Operations Research Society of Japan, 2004

    work page 2004

  21. [21]

    Assembly-like queues with finite capacity: bounds, asymptotics and approximations,

    E. Lipper and B. Sengupta, “Assembly-like queues with finite capacity: bounds, asymptotics and approximations,” Queueing Systems, 1986

    work page 1986

  22. [22]

    Poisson arrivals see time averages,

    R. W. Wolff, “Poisson arrivals see time averages,” Operations Research, vol. 30, no. 2, pp. 223–231, 1982

    work page 1982

  23. [23]

    On a generalized m/g/1 queuing process in which the first customer of each busy period receives exceptional service,

    P. D. Welch, “On a generalized m/g/1 queuing process in which the first customer of each busy period receives exceptional service,” Operations Research, vol. 12, no. 5, pp. 736–752, 1964

    work page 1964