A Shuffling Framework for Local Differential Privacy
This work addresses privacy risks in LDP for data analysts by offering a tunable solution to prevent inference attacks while maintaining some data utility, representing an incremental improvement over existing shuffle DP methods.
The paper tackles the vulnerability of local differential privacy (LDP) deployments to inference attacks by proposing a shuffling framework that balances privacy and data learnability, introducing d-sigma-privacy to formalize this trade-off and demonstrating its practicality on real-world datasets.
ldp deployments are vulnerable to inference attacks as an adversary can link the noisy responses to their identity and subsequently, auxiliary information using the order of the data. An alternative model, shuffle DP, prevents this by shuffling the noisy responses uniformly at random. However, this limits the data learnability -- only symmetric functions (input order agnostic) can be learned. In this paper, we strike a balance and show that systematic shuffling of the noisy responses can thwart specific inference attacks while retaining some meaningful data learnability. To this end, we propose a novel privacy guarantee, d-sigma-privacy, that captures the privacy of the order of a data sequence. d-sigma-privacy allows tuning the granularity at which the ordinal information is maintained, which formalizes the degree the resistance to inference attacks trading it off with data learnability. Additionally, we propose a novel shuffling mechanism that can achieve \name-privacy and demonstrate the practicality of our mechanism via evaluation on real-world datasets.