Between Close Enough to Reveal and Far Enough to Protect: a New Privacy Region for Correlated Data

Luis Maßny, Rawad Bitar, Fangwei Ye, Salim El Rouayheb

Introduction

In modern data ecosystems, individual privacy is increasingly threatened by the inherent correlations between data points. Whether it is location history shared among coworkers or genetic markers shared among relatives, data is rarely independent. This creates a fundamental "Opt-Out" paradox: even if a user chooses to withhold their data or requests to be forgotten, an adversary can often reconstruct their private information by analyzing the records of correlated neighbors. Standard Differential Privacy (DP) frameworks, which typically assume record independence, fail to provide adequate protection in these scenarios.

The Challenge of Correlated Data

When a "private" user $X_p$ opts out of a dataset, simply erasing their record is insufficient. Existing solutions often involve redacting a window of data around the private record to mitigate leakage. However, these traditional methods are largely data-independent, meaning they redact the same volume of information regardless of the actual data values. This leads to a significant "utility problem," where safe, non-informative data is discarded simply because it might have been risky in a worst-case scenario. This paper introduces the 3R mechanism, a data-dependent approach that leverages specific data realizations to maximize utility while maintaining strict privacy guarantees.

The 3R Mechanism: A Pointwise-Influence Approach

The core innovation of the 3R mechanism is the shift from max-influence to pointwise-influence. Traditional methods ask what the maximum possible information a record could leak across all possible values. In contrast, the 3R mechanism asks how much a specific realization (e.g., a '0' or a '1') leaks about the private user.

Classification of records into Safe (S), Medium (M), and Large (L) influence regions based on pointwise-influence curves.

By modeling data correlation as a stationary Markov process, the authors categorize records into three distinct regions:

  1. Safe (S): Records with low influence that are always released.
  2. Medium (M): Records with moderate influence that are released or redacted probabilistically based on their specific value to "balance" privacy leakage.
  3. Large (L): High-influence records that are always redacted.

This categorization allows the mechanism to find a "sweet spot" through convex optimization, maximizing the amount of data released within a defined privacy budget $\epsilon$.

Key Results and Utility Gains

The authors demonstrate that data-independent mechanisms, such as the popular "Markov Quilt" approach, are fundamentally limited because they ignore the specific values of the data. The 3R mechanism's ability to utilize the "Medium" region—by being more likely to release less informative values—results in substantial utility improvements.

Utility comparison between the 3R mechanism and the theoretical upper bound for data-independent mechanisms (DIM-UB) across varying privacy budgets.

Numerical simulations using synthetic Markov chain data show that the 3R mechanism consistently outperforms the theoretical upper bounds of all data-independent mechanisms. For instance, in a simple two-record case where traditional methods would require total redaction (0% utility) to meet a privacy target, the 3R mechanism achieved approximately 29% utility under the same guarantee. Furthermore, the authors prove that as the number of records $n$ grows, the 3R mechanism is asymptotically guaranteed to outperform state-of-the-art baselines.

Conclusion and Future Work

The 3R mechanism represents a significant step forward in handling correlated data privacy by moving beyond the conservative constraints of data-independent redaction. While currently optimized for binary Markovian data, the framework provides a foundation for more complex scenarios. Future research will explore extending these principles to continuous data types and more intricate correlation structures, such as social media graphs, to further bridge the gap between data utility and individual privacy.

Summary updated

Abstract

When users make personal privacy choices, correlation between their data can cause inadvertent leakage about users who do not want to share their data by other users sharing their data. As a solution, we consider local redaction mechanisms. As prior works proposed data-independent privatization mechanisms, we study the family of data-independent local redaction mechanisms and upper-bound their utility when data correlation is modeled by a stationary Markov process. In contrast, we derive a novel data-dependent mechanism, which improves the utility by leveraging a data-dependent leakage measure.
BibTeX
@inproceedings{many2025between,
  author = {Luis Maßny and Rawad Bitar and Fangwei Ye and Salim El Rouayheb},
  title = {{Between Close Enough to Reveal and Far Enough to Protect: a New Privacy Region for Correlated Data}},
  booktitle = {ITW},
  year = {2025},
  doi = {10.1109/itw62417.2025.11240504},
}
Figure