- d-convergence: A novel paradigm for quantifying privacy in the age of Big-Data
Abstract
In this paper, we develop a user-centric privacy framework for quantitatively assessing the exposure of personal information in open settings. Our formalization addresses key challenges posed by such open settings, such as the unstructured dissemination of heterogeneous information and the necessity of user- and context-dependent privacy requirements. We propose a new definition of information sensitivity derived from our formalization of privacy requirements, and, as a sanity check, show that hard non-disclosure guarantees are impossible to achieve in open settings. After that, we provide an instantiation of our framework to address the identity disclosure problem, leading to the novel notion of $d$-convergence. $d$-convergence is based on indistinguishability of entities and it bounds the likelihood with which an adversary successfully links two profiles of the same user across online communities. Finally, we provide a large-scale evaluation of our framework on a collection of 15 million comments collected from the Online Social Network Reddit. Our evaluation validates the notion of $d$-convergence for assessing the linkability of entities in our data set and provides deeper insights into the data set's structure.
Introduction
Historically, privacy research has focused on "closed-world" settings: centralized databases with structured columns, such as hospital patient records or census data. In these environments, a central authority can sanitize data before publication using models like $k$-anonymity or Differential Privacy. However, the modern internet represents an "open-world" setting. Users scatter unstructured, heterogeneous data—tweets, comments, and likes—across multiple platforms without a central authority to manage noise or sanitization.
In such an environment, what constitutes "sensitive" information is highly context-dependent. Because global data sanitization is impossible in open settings, there is a critical need for a mathematical methodology to measure the privacy risks users face, specifically regarding identity disclosure—the ability of an adversary to link a pseudonymous profile back to a real identity or another profile.
The Impossibility of Hard Guarantees
A primary contribution of this work is the formalization of privacy requirements for the open web. We provide a mathematical proof demonstrating that hard non-disclosure guarantees, such as $\epsilon$-semantic privacy (a generalized form of differential privacy), are impossible to achieve in open settings. Specifically, we show that $\epsilon$-semantic privacy can only hold for $\epsilon = 1$ when adversaries can directly observe public information and leverage arbitrary background knowledge. This finding necessitates a shift in the security community from enforcing strict privacy to assessing probabilistic risk.
The $d$-convergence Framework
To address identity disclosure, we introduce the novel notion of $d$-convergence. This framework moves away from the idea of hiding data and instead focuses on the user's ability to "hide in a crowd."
$(k, d)$-anonymity
We define a group of entities as "$d$-convergent" if they are all within a mathematical distance $d$ of each other in a high-dimensional feature space. A user achieves $(k, d)$-anonymity if they belong to a $d$-convergent subset of at least $k$ similar users. By representing user behavior (such as writing style) as a statistical model, privacy becomes a geometric problem: the closer a user is to a cluster of other users, the lower the probability of unique identification.
Experimental Methodology
We evaluated the framework using a massive dataset of user-generated text from Reddit, collected in September 2014.
- Data Scope: The evaluation focused on a subset of 15 million comments. To ensure statistical significance, we filtered for "interesting profiles," resulting in 58,091 profiles belonging to 37,935 users across 1,930 subreddits.
- Profile Modeling: User profiles were modeled using unigrams (word frequencies). To calculate the "distance" between writing styles, we employed the Jensen-Shannon divergence, a method for measuring the similarity between probability distributions.
- Ground Truth: To simulate an adversary linking accounts across different social networks, we treated each subreddit as an isolated community. Since Reddit users maintain the same username across subreddits, we possessed a perfect ground truth to verify if the $d$-convergence model could successfully link a user's profile in "Subreddit A" to their profile in "Subreddit B."
Key Results
Our empirical evaluation validated $d$-convergence as a robust metric for assessing linkability:
- Behavioral Consistency: Profiles belonging to the same user across different subreddits were measurably closer to each other in the feature space than to profiles of different users, confirming that writing style is a viable biometric for identity disclosure.
- Crowd Size and Risk: We measured the adversary's success using
precision@5(the probability of the true match appearing in the adversary's top 5 guesses). The results showed a clear inverse correlation: as the size of a user's anonymous subset ($k$) increased, the adversary's precision dropped significantly. This demonstrates that blending into a larger, $d$-convergent crowd mathematically mitigates the risk of being linked.
Conclusion and Future Work
The $d$-convergence framework provides a foundation for user-centric privacy tools in the age of Big Data. By moving from enforcement to assessment, we can provide users with accurate risk profiles of their digital footprints.
Future work will focus on the temporal dynamics of data—acknowledging that information sensitivity often decays over time—and developing more sophisticated profile models beyond simple word frequencies. Ultimately, this research aims to empower users with tools that warn them when their online contributions make them uniquely identifiable within the digital crowd.
Summary updated