TL;DR
This paper introduces a novel mechanism for securely sharing private data across networks, where the level of privacy is dynamically adjusted based on the "distance" between users. This approach allows for the inference of global network statistics while ensuring that individual privacy is protected, even against coordinated attacks from groups of users.
What Problem Does This Paper Address?
In today's interconnected world, social and technological networks facilitate the rapid sharing of vast amounts of data. This convenience, however, comes with significant privacy concerns. Private information can be inadvertently leaked or inferred, especially in social networks where users might share more with friends than strangers. This problem is compounded by the fact that a friend's friend can also access your data, creating a cascading privacy risk. Existing privacy mechanisms often offer a one-size-fits-all approach or focus on protecting individual data components. This paper tackles the challenge of diffusing private data across a network while respecting varying privacy needs based on user proximity and preventing malicious coalitions from compromising privacy.
Methods
The core of this paper's contribution lies in a privacy-preserving mechanism that leverages differential privacy and a stochastic process. The mechanism ensures that when user A wants to access user B's private data, the response is differentially private, with the privacy guarantee quantified by the distance between A and B in the network graph. Specifically, closer users receive less stringent privacy guarantees (allowing for more accurate data), while distant users receive stronger privacy guarantees (more noise, less accuracy).
The proposed mechanism is built upon a composite process that generates responses. A key innovation is the use of a continuous-domain stochastic process that is "lazy," meaning it remains constant over small intervals of privacy levels. This "laziness" allows for efficient sampling and storage. The authors also introduce a novel approach to handle coalition attacks, where a group of users might combine their responses to infer more about the private data. Their mechanism ensures that such coalitions cannot gain more information than the individual user with the loosest privacy guarantee within the coalition.
Datasets
- Synthetic Network: A synthetic network with 150 nodes and 1256 edges was used to demonstrate the diffusion of private GPS coordinates.
- Facebook Ego-Network: A real-world Facebook ego-network was used to illustrate the diffusion of a user's infection status (a binary bit).
Key Insights and Ideas
- Distance-Based Privacy: The idea that privacy should not be binary (private vs. public) but rather a spectrum that scales with proximity in a network is a crucial insight. This allows for a more nuanced and practical approach to data sharing.
- Stochastic Process for Privacy: Using a stochastic process to generate differentially private responses is an elegant way to introduce controlled noise that varies with privacy levels. The "lazy" nature of this process is key to its efficiency.
- Coalition Resilience: The mechanism's ability to prevent coalitions of users from compromising privacy is a significant advancement. This addresses a critical vulnerability in many existing privacy-preserving systems.
- Global Statistics with Local Privacy: The paper demonstrates that it's possible to enable network analysts to infer global statistics (like epidemic spread) while still protecting individual users' sensitive information.
Key Results
- The proposed mechanism provides ε(dij)-differential privacy, where ε is a decreasing function of the distance dij between users.
- The expected squared-error of the response Yij is proportional to n(n+1)/ε(dij)², meaning accuracy depends solely on the privacy level (and thus distance), not network topology or size.
- The mechanism is proven to be coalition-resilient, meaning no group of users can obtain more information than the user with the weakest privacy guarantee in the group.
- Algorithmic implementations are provided with complexity dependent on the extreme privacy levels, not the network size, making them scalable.
Limitations and Future Work
- Central Authority for Distances: The current model assumes the existence of a central authority to compute distances between users. The authors acknowledge that future work could explore decentralized methods for distance computation.
- Honest-but-Curious Model: The implementation assumes an honest-but-curious model for communication channels. Real-world scenarios might involve more adversarial communication.
- Joint Problem of Estimation and Privacy: While this work focuses on privacy, the authors suggest future research should address the joint problem of accurately estimating global quantities while preserving privacy.
Summary updated