Sparse privacy methods improve discrete data protection techniques
Sparse Kernel Mechanisms for Locally Differentially Private Discrete Channels
Information Theory
Summary
This paper looks at how to protect private information when data is shared in ways that add some randomness to hide exact details. The authors study mechanisms that only use a small number of possible outputs compared to all data possibilities, aiming to keep privacy while making the system simpler. They find that if the privacy rules are very strict, the available outputs can't change with the input data, but if the rules allow a bit more flexibility, the outputs can vary while balancing privacy and data use. The paper also gives formulas to understand how much privacy is lost depending on the design and tests these on several example techniques.
What this means in practice
- •For data privacy engineers: Design data-sharing systems that add noise selectively to preserve user privacy with flexible output choices related to input data features.
- •For network security teams: Implement efficient discrete privacy mechanisms with controlled output supports to protect communication data from local privacy attacks.
Authors
Amirreza Zamani, Parastoo Sadeghi, Mikael Skoglund
Abstract
We study sparse locally private discrete mechanisms generated by a nonnegative kernel and an input-dependent admissible output support. The support set is intentionally small relative to the ambient alphabet and acts as a mechanism-design parameter. This formulation covers metric-ball supports, sparse exponential mechanisms, sparse staircase mechanisms, sparse randomized response, sparse additive kernels such as Skellam perturbations, and Poisson-binomial-inspired bounded-support channels. We give a general exact characterization of pure and approximate local differential privacy for this sparse-kernel class. Pure local differential privacy forces all supports to coincide, so genuinely input-dependent sparse supports are incompatible with pure privacy. In the approximate regime, the privacy defect decomposes exactly into support leakage and overlap excess loss. We instantiate the formula for several discrete mechanism families. For sparse staircase mechanisms, a shell-ratio condition eliminates overlap excess loss. For graph-metric supports, overlap of metric balls is necessary for nontrivial privacy. For sparse randomized response, the support-leakage term has a closed form in terms of support mismatch. For generic radius-truncated additive kernels and, in particular, sparse Skellam mechanisms, we obtain exact finite-support formulas in terms of the Skellam CDF and an exact Bessel-ratio overlap condition. Numerical evaluations illustrate how support radius and kernel shape separately affect support leakage and overlap excess loss.