Revisiting a combinatorial approach toward measuring anonymity

Benedikt Gierlichs, Carmela Troncoso, Claudia Díaz, Bart Preneel, Ingrid VerbauwhedeWPES 2008 · DOI

TL;DR

This paper revisits a combinatorial metric for measuring anonymity in communication systems, arguing that it overestimates anonymity when users send or receive multiple messages. The authors propose a generalized metric that accounts for these multiplicities and present a divide-and-conquer algorithm to compute it, offering a more accurate assessment of privacy.

What Problem Does This Paper Address?

Anonymous communication systems, like mixes and onion routers, aim to obscure the links between message senders and receivers. Evaluating the effectiveness of these systems requires robust anonymity metrics. Edman et al. proposed a combinatorial metric based on the number of possible perfect matchings in a bipartite graph representing the system's inputs and outputs. However, this metric assumes each sender and receiver is involved in exactly one communication. This assumption breaks down in real-world scenarios where users can send or receive multiple messages, leading to an overestimation of anonymity. This paper addresses this gap by proposing a refined metric that correctly accounts for these multiplicities, providing a more realistic measure of privacy.

Methods

The core of the paper is the generalization of Edman et al.'s anonymity metric. The original metric relies on the permanent of an adjacency matrix representing a bipartite graph of inputs and outputs, where a perfect matching signifies a one-to-one correspondence. The authors introduce the concept of "equivalence classes" of perfect matchings. These classes group matchings that result in the same sender-receiver relationships, even if the underlying input-output links differ.

When users send/receive multiple messages, these equivalence classes can have different sizes. The paper proposes a generalized metric that uses Shannon entropy to quantify the uncertainty an adversary faces in identifying the correct sender-receiver relationship, considering the varying sizes of these equivalence classes.

To compute this generalized metric, the authors develop a divide-and-conquer algorithm. This algorithm recursively explores possible sender-receiver assignments, building a tree where nodes represent intermediate states and edges represent assignment probabilities. The algorithm efficiently calculates the number of equivalence classes and their cardinalities, avoiding the computationally infeasible brute-force enumeration of all perfect matchings.

Datasets

Not discussed in the paper. The paper uses theoretical examples and scenarios to illustrate its concepts and algorithms.

Key Insights and Ideas

  • Sender/Receiver Multiplicities Matter: The most crucial insight is that anonymity metrics must account for users sending or receiving multiple messages. The original combinatorial metric fails to capture the anonymity loss incurred in such scenarios.
  • Focus on Sender-Receiver Relationships: The paper emphasizes that the true goal of anonymity is to hide sender-receiver relationships, not just input-output links. This shift in focus necessitates a different approach to metric design.
  • Equivalence Classes for Robustness: The concept of equivalence classes of perfect matchings is key to generalizing the metric. It allows grouping indistinguishable sender-receiver relationships, leading to a more accurate anonymity assessment.
  • Entropy for Uncertainty: Using Shannon entropy to measure the adversary's uncertainty over these equivalence classes provides a principled way to quantify anonymity when class sizes vary.
  • Divide and Conquer for Efficiency: The proposed algorithm offers a significant improvement over brute-force methods for computing the generalized metric, making it more practical for analysis.

Key Results

  • The paper demonstrates with an example (Figure 2) that the original metric assigns maximal anonymity (d(A)=1) to a scenario with multiple messages, while the generalized metric correctly identifies a reduced anonymity level (d*=0.61).
  • For a complete graph scenario with multiplicities on both sender and receiver sides (Figure 3), the generalized metric evaluates to d*(A) = 0.31, significantly lower than the original metric's d(A)=1.
  • The paper provides upper and lower bounds for the generalized anonymity metric in the case of complete graphs, offering analytical insights even without running the full algorithm. For the example in Figure 3, the bounds were d(A) ≥ 0.14 and d(A) ≤ 0.48.

Limitations and Future Work

  • Algorithm Complexity: While the proposed divide-and-conquer algorithm is more efficient than exhaustive search, it can still become computationally expensive for very large values of t (the number of inputs/outputs). The authors acknowledge that specifying a more efficient algorithm remains an open problem.
  • Generalization to Arbitrary Graphs: The paper focuses on generalizing the metric and provides bounds for complete graphs. Further research could explore more efficient computation for arbitrary graph structures.
  • Practical Applicability: While the metric is theoretically sound, its direct application to real-world systems might require careful modeling of user behavior and communication patterns.

Summary updated

BibTeX
@inproceedings{gierlichs2008revisiting,
  author = {Benedikt Gierlichs and Carmela Troncoso and Claudia Díaz and Bart Preneel and Ingrid Verbauwhede},
  title = {{Revisiting a combinatorial approach toward measuring anonymity}},
  booktitle = {WPES},
  year = {2008},
  doi = {10.1145/1456403.1456422},
}
Figure