Anonymity metrics

Definition:
An anonymity metric indicates the uncertainty of the identity of a fixed entity is , from the point of view by advarsary A.

Objective function

This should include two ingredients , i.e. anonymity level and anonymity loss.

Anonymity level

Anonymity level depends on: 1) distribution of probabilities (see towards measuring anonymity) ; 2) size of anonymity set (see A system for anonymous and unobservable internet access & The disadvantages of free mix routes and how to overcome them in Hannes Federath)

• Edman et al. orginally propose to count the number of possible perfect matching in G , i.e. computing the permanent of the adjacency matrix A.
  (see Revisiting combinational methods )

Computing the anonymity degree of stratified network

For statified network , mixes are arranged in a fixed number of layers where each mix is assigned to specific layer at any given time.

we should make assumptions on the attacker at first.(i.e. Internal , Passive and local )

• Internal attacker : controls some of the entities within the system.
• Passive attacker : corrupted mixes can listen to communication , gain no extra information of the users
• Local attacker : controls a subset of mixes ,and cannot perform any traffic analysis on the rest of the system.

Denotion beforehand

Vector of mixes(nodes) := M1,M2…M_k

Number of layers := L

Number of ingress provider := I

Number of egress provider := O

Buckets( nodes in a layer ) := k/L

Define entropy of stratified network

We begin calculating the anonymity level by defining its entropy fomula , i.e.

$$H(X)=\sum _{i=1}^k(p_i\ast lg(\frac{1}{p_i}))$$

Where

$p_i$ indicates the probability of each possible value that X may take of the anonymity Set ,in this case , N := k + L . i.e. the size of anonymity set .

Thus ,

$H_M=:lo{g}_2(k+L)$ where

$H_M$ denotes the maximum entropy.

Degree of anonymity

We define the degree of anonymity provided by the system as :

$$d=1-\frac{H_M-H(X)}{H_M}=\frac{H(X)}{H_M}$$

We assume Adversary compromise nodes in two fasions , i.e. randomly & targeted.

Anonymity loss

(see Measuring relationship anonymity in mix networks)

• route selection
  In a stratified network like Meson , route selection is restriced to a subset of mixes at each hop, meaning provides better anonymity than free-route network.

As the number of sender approaches the number of mixes, the stratified network go better because the number of feasible routes get smaller. Then the anonymity loss due to non-uniform destination dominates the effects of route selection when the number of routes increases.