PreprintarXiv licencearXiv
The Right to Be Forgotten under Correlation: Privacy-Utility Tradeoffs
Abstract
We study privacy-preserving algorithms that redact information from a correlated dataset. The goal is to reduce the information leakage about sensitive parts. We analytically characterize the optimal tradeoff between privacy (leakage through correlation) and utility (number of redactions) for local mechanisms and binary Markovian correlations. Our result shows how to decompose the mechanism design problem into a sequence of local mechanism design problems and reveals their sequential relation. The optimal mechanism is the solution to a Finite-Horizon Deterministic Markov Decision Process.
Related
- Diffusion Sensitivity Geometry and Strong Duality for Optimal Privacy-Utility Tradeoffs
- Performative Privacy: When Differential Privacy Maximizes Utility
- On Privacy Mechanism Design Under a Bounded α-Lift Leakage Constraint with χ2-Utility
- BCFL-DAI-PUB: Blockchain-integrated federated learning with dynamic adaptive incentives for privacy-utility balanced credit risk modelling
- Exact Storage-Repair-Bandwidth Tradeoffs for (6,5,5) and (7,6,6) Exact-Repair Regenerating Codes
BibTeX
@misc{massny2026right,
title = {{The Right to Be Forgotten under Correlation: Privacy-Utility Tradeoffs}},
author = {Luis Massny and Rawad Bitar and Fangwei Ye and Salim El Rouayheb},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17088},
eprint = {2610.17088},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17088},
}
RIS
TY - UNPB
TI - The Right to Be Forgotten under Correlation: Privacy-Utility Tradeoffs
AU - Luis Massny
AU - Rawad Bitar
AU - Fangwei Ye
AU - Salim El Rouayheb
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.17088
UR - https://arxiv.org/abs/2610.17088
AB - We study privacy-preserving algorithms that redact information from a correlated dataset. The goal is to reduce the information leakage about sensitive parts. We analytically characterize the optimal tradeoff between privacy (leakage through correlation) and utility (number of redactions) for local mechanisms and binary Markovian correlations. Our result shows how to decompose the mechanism design problem into a sequence of local mechanism design problems and reveals their sequential relation. The optimal mechanism is the solution to a Finite-Horizon Deterministic Markov Decision Process.
ER -