Introduction

<aside> 💡

Additional numerical results are provide in the Appendix.

</aside>

We consider an anonymous communication system where a message is sent through $k$ mix nodes which are sampled from $N$ nodes of a network where $M$ nodes are adversarial. Presence of adversarial nodes in a communication path can cause anonymity or communication failure. The probability of anonymity failure is approx. $(M/N)^k$ and the probability of communication failure is approx. $1-(1-M/N)^k$ when a single comm. path is sampled with (or without) replacement. However, when $n$ send messages are sent through randomly selected (with replacement) $k$-paths the number of paths with anonymity (or communication) failure deviates from the average $n(M/N)^k$ (or $n(1-(1-M/N)^k)$) and we estimate probability of these deviations for its given magnitude. Furthermore, we consider “structural” properties of random structures induced by a number of $k$-paths. In particular we study sizes of intersections and properties of random factor graphs. The former allows us to quantify the “intersection attack” and the latter allows us to reason about general anonymity properties. Finally, we propose a structurally homogenous (random) anonymous communication system based on a random regular factor graph.

Analysis of failures

Sampling without replacement

We consider the design of mix gadget proposed in the document
In this section, we consider the selection of $k$ nodes from a population of $N$ nodes without replacement. We assume that there are $M$ adversarial nodes.
Anonymity failure occurs when all $k$ sampled nodes are adversarial. The probability of anonymity failure is given by

$$ \frac{{N-k\choose M-k}}{{N\choose M}}=\frac{{M\choose k}}{{N\choose k}} $$

Furthermore, using bounds on binomial coefficients, converted to natural base of logarithm, we have

$$ \frac{{N-k\choose M-k}}{{N\choose M}}\leq\sqrt{\frac{N-k}{N}\frac{4M}{\pi(M-k)}}\exp\left[(N-k)\mathrm{H}\left(\frac{M-k}{N-k}\right)-N\mathrm{H}\left(\frac{M}{N}\right)\right], $$

where $H(P)=-(1-P)\log(1-P)-P\log(P)$ is the binary entropy of probability $P$. [Proof provided in the Appendix]

Assuming $0<M/N<1$, i.e. $M/N=P$ is fixed, and constant $k$ such that $k/N\rightarrow0$ when $N\rightarrow\infty$, the above gives us

$$ \frac{{N-k\choose M-k}}{{N\choose M}}\leq\frac{2}{\sqrt{\pi}}\left(\frac{M}{N}\right)^k, $$

i.e. the asymptotic upper bound for the prob. of anonymity failure. [Proof provided in the Appendix]

The probability of anonymity failure is plotted below.

$The probability of anonymity failure as a function of k plotted for $N=10$ (square symbols) and $N=10^2$ (+ symbols) nodes with $1/2$ adversarial nodes. The symbols in black colour are results of exact computation and the symbols in red colour are bounds. The red line is the asymptotic upper bound $\frac{2}{\sqrt{\pi}}\left(\frac{M}{N}\right)^k$. Note that (natural) log scale was used in the y-axis.$

The probability of anonymity failure as a function of k plotted for $N=10$ (square symbols) and $N=10^2$ (+ symbols) nodes with $1/2$ adversarial nodes. The symbols in black colour are results of exact computation and the symbols in red colour are bounds. The red line is the asymptotic upper bound $\frac{2}{\sqrt{\pi}}\left(\frac{M}{N}\right)^k$. Note that (natural) log scale was used in the y-axis.