Owner: @Alexander Mozeika

Introduction

• We consider statistical mechanics (SM) approach to anonymous communication (AC) which builds on previous work. The latter suggests using correlations to measure anonymity.
• Advantage of SM is that it shifts the perspective from a purely cryptographic one to a systems-based one, focusing on uncertainty**,** entropy**,** and noise within a large population of nodes.

Assumptions

• The set of mix nodes $\mathcal{V} = \{1, \ldots, N\}$ .
• The set of real messages $\mathcal{M}R = \{m_1, m_2,\ldots,m{N_R}\}$, where $N_R$ is the number of real messages.
• The set of cover messages $\mathcal{M}C = \{c_1, c_2,\ldots,c{N_C}\}$, where $N_C$ is the number of cover messages.
• Encryption ensures that messages are indistinguishable from each other. The latter is facilitated by cryptographic transformation of messages.
• The set of all messages $\mathcal{M} = \mathcal{M}_R \cup \mathcal{M}_C$
• The undirected (or directed) graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ modelling communication network.

Definitions

• For message $m\in \mathcal{M}$ we define the path $P_m = (v_{m,1}, v_{m,2}, ..., v_{m,L(m)})$, where $L(m)$ is the length of the path.
• Here $v_{m,1} \in \mathcal{V}$ is the origin and $v_{m,L(m)} \in \mathcal{V}$ is the final node.
• For any $(v_{m,k}, v_{m,k+1})\in P_m$ we have that $(v_{m,k}, v_{m,k+1}) \in \mathcal{E}$. The latter condition can be relaxed if a node in $\mathcal{V}$ can send a message to any other node in $\mathcal{V}$.
• The timeline $T_m = (t_{m,1}, t_{m,2}, ..., t_{m,L(m)-1})$, where $t_{m,i}$ is the time at which message $m$ was sent from node $v_i$ to node $v_{i+1}$.
• We note that $t_{m,1} \leq t_{m,2} \leq \cdots\leq t_{m,L(m)-1}$.

$$ v_1 \xrightarrow{\scriptstyle t_1} v_2 \xrightarrow{\scriptstyle t_2} \cdots \xrightarrow{\scriptstyle t_{L-1}}v_L\\\vdots \\\tilde{v}_1 \xrightarrow{\scriptstyle \tilde{t}_1} \tilde{v}_2 \xrightarrow{\scriptstyle \tilde{t}2} \cdots \xrightarrow{\scriptstyle \tilde{t}{L-1}}\tilde{v}_L $$

• The pair $(P_m, T_m)$ for a message $m$ defines its (spatiotemporal) trajectory.
• The set of these trajectories for all messages $\omega=\{ (P_m, T_m) \mid \forall m \in \mathcal{M} \}$ is the microstate.