Composition Attack: The "Hidden Fingerprint" Linking Your Social Personas

TL;DR

Even if your identity is scrubbed and "anonymized" on Facebook and LinkedIn separately, the way you connect with others creates a unique structural signature. This paper explores the Composition Attack, a method that links your accounts across different platforms by comparing your relative "popularity" (degree) and your attributes, reaching a 20%-33% success rate even without prior background knowledge.

Background: The Multi-Networking Trap

Modern privacy preserving techniques are usually designed in a vacuum—assuming an attacker only has access to one dataset. But in reality, users are "multi-homing." If you exist in Network A and Network B, an attacker can use the overlap to break the anonymity of both. This paper moves the concept of Composition Attacks from simple tables (Relational Data) to complex social graphs.

The Core Insight: The Topological Fingerprint

The author relies on two key behavioral assumptions:

1. Relative Popularity is Constant: If you are an extrovert with 10x more friends than the average user on X (Twitter), you likely have 10x more friends than average on Threads.
2. Relationship Persistence: If two people are friends on one platform and both join a second platform, they are highly likely to connect there as well.

Based on this, the author defines a Sensitive Value $S(v)$: $S(v)=\frac{deg(v)}{A(G^{\ast })}$ Where $deg(v)$ is your number of connections and $A(G^{\ast })$ is the average number of connections in that specific network. This ratio becomes a "fingerprint" that stays stable across different platforms.

Methodology: The Two-Stage Attack

The proposed attack doesn't require the attacker to know who you are initially; it only aims to find which node in Network G1 matches which node in Network G2.

1. Preprocessing & Matching

The attacker first identifies Attribute Equivalence Classes. For example, if a node's anonymized attributes are "Age: 20-30, Gender: Male," they look for nodes in the second network with the same range. Within these groups, they filter for nodes where the Sensitive Value $S(v)$ matches within a small tolerance ($\delta$).

2. Structural Pruning (Reducing Cardinality)

To filter out "False Positives," the algorithm looks at the neighbors. If the algorithm suspects $(v_1,w_1)$ and $(v_2,w_2)$ are the same people, it checks if $v_1$ is connected to $v_2$ in the first graph AND $w_1$ is connected to $w_2$ in the second. If the structure doesn't match, the pair is discarded.

Figure: How an auxiliary subgraph is transferred from a compromised network to deanonymize a second network.

Experimental Validation

The paper utilizes Scale-Free Networks generated via the Barabási-Albert model to simulate real-world social dynamics.

Key Findings:

• Scale Matters: Paradoxically, larger graphs make the attack more accurate (up to 33% TPrate for 400+ nodes), likely because the distribution of degrees becomes more distinct.
• Density is the Enemy: As networks become denser (higher average degree), the "noise" increases, making it harder to find the true corresponding vertices.
• Anonymity vs. Utility: Increasing $k$ in k-anonymity (making more people look the same) drops the attack success. However, even at $k=5$, the attack still performs better than random guessing.

Figure: The impact of graph size, density, and k-anonymity on attack accuracy.

Critical Analysis & Future Outlook

The most striking takeaway is the Self-Information Leakage. Even if a data provider does everything right (removing names, blurring ages), the user's own social behavior—specifically their relative degree—remains a persistent identifier.

Limitations: The study is limited to synthetic networks and small sizes (up to 450 nodes) due to computational constraints ($O(R^2)$ complexity). In the real world, "Average Degree" might fluctuate more wildly between a professional network (LinkedIn) and a personal one (Instagram).

Conclusion: As we move toward more open data sharing, this research proves that we cannot protect privacy by looking at one dataset in isolation. The "Composition Attack" is a potent reminder that our data exists in an ecosystem, and our structural patterns are harder to hide than our names.