Owner: 🟢 @Alexander Mozeika

Reviewer: 🟢 @Marvin Jones 🟢 @Álvaro Castro-Castilla

Introduction

<aside> 💡

Details of mathematical derivations, with references to literature, and additional numerical results are in the Appendix.

</aside>

We consider anonymous communication system which uses a layered network of mix nodes, i.e. the mix network. We assume that nodes are used in the mix network are sampled from $N$ nodes of a network where $M$ nodes are adversarial. Presence of adversarial nodes in a communication path of the mix network can cause anonymity or communication failure. For anonymity failure to occur in a communication path all mix nodes on this path have to be adversarial and such path is compromised. In a mix network with $L$ layers naive reasoning (e.g. see the article) gives $(M/N)^L$ for the fraction of compromised paths. The latter is correct for a mix network of infinite width, but when the width is finite the fraction of compromised paths can be significantly larger than $(M/N)^L$. In this document we study statistical properties of the fraction compromised paths. Result of this work allows us to estimate the probability that the fraction of compromised paths is greater than some threshold. The latter can be used to optimise layered mix networks.

Assumptions

Failures

Screenshot 2024-03-04 at 12.49.16.png