Source-linked AI summary
Individual Differential Privacy: A Utility-Preserving Formulation of Differential Privacy Guarantees
Jordi Soria-Comas, Josep Domingo-Ferrer, David Sánchez, David Megías
TL;DR
Standard differential privacy can impose more distortion than its intuitive individual-level guarantee requires, limiting analytical utility. The paper proposes individual differential privacy, which compares the actual data set with its neighbors and uses local sensitivity to reduce noise; it reports improved accuracy while preserving the individual-level guarantee.
Problem
Standard differential privacy requires indistinguishability for every pair of neighboring data sets, which can cause significant accuracy loss despite the intuitive guarantee concerning an actual data set and its neighbors.
Method
The paper formalizes individual differential privacy and proposes mechanisms that exploit the actual data set, including local-sensitivity calibration for numerical queries.
Results
Individual differential privacy reduces query noise and substantially improves accuracy while maintaining the intuitive disclosure-limitation guarantee for individuals.
Takeaways & Limitations
Individual differential privacy can provide a utility-preserving alternative where standard differential privacy is not viable, while retaining individual-level privacy guarantees.
Takeaways & Limitations
Smooth-sensitivity calibration requires heavy-tailed admissible noise distributions, limiting that standard-DP accuracy approach.
Abstract
from arXiv · showhide
Differential privacy is a popular privacy model within the research community because of the strong privacy guarantee it offers, namely that the presence or absence of any individual in a data set does not significantly influence the results of analyses on the data set. However, enforcing this strict guarantee in practice significantly distorts data and/or limits data uses, thus diminishing the analytical utility of the differentially private results. In an attempt to address this shortcoming, several relaxations of differential privacy have been proposed that trade off privacy guarantees for improved data utility. In this work, we argue that the standard formalization of differential privacy is stricter than required by the intuitive privacy guarantee it seeks. In particular, the standard formalization requires indistinguishability of results between any pair of neighbor data sets, while indistinguishability between the actual data set and its neighbor data sets should be enough. This limits the data controller's ability to adjust the level of protection to the actual data, hence resulting in significant accuracy loss. In this respect, we propose individual differential privacy, an alternative differential privacy notion that offers em the same privacy guarantees as standard differential privacy to individuals (even though not to groups of individuals). This new notion allows the data controller to adjust the distortion to the actual data set, which results in less distortion and more analytical accuracy. We propose several mechanisms to attain individual differential privacy and we compare the new notion against standard differential privacy in terms of the accuracy of the analytical results.
1 Introduction
Differential privacy protects individuals in interactive analyses, but its strict formulation can substantially reduce utility. The paper proposes individual differential privacy, which limits protection to individuals in the actual data set and uses that knowledge to reduce distortion.
- Protection setting: Interactive protection answers user queries on original data and can adjust protection to the analysis, maximizing result accuracy.Non-interactive protection releases a protected data set before the analysis is known.
- Motivation: Differential privacy makes disclosures equally likely whether or not a particular individual contributes data, but deployment remains limited because accuracy is often poor.The utility problem is especially acute except for queries stable to record modification.
- Problem: The standard formulation is stronger than the intuitive guarantee because it also protects groups and forbids the trusted party from using knowledge of the actual data set when adding noise.The paper argues that these requirements increase distortion and reduce the usefulness of protected results.
- Contribution: Individual differential privacy protects individuals in the data set rather than groups, allowing the trusted party to reduce distortion using the actual data set.The paper presents this as a formalization aligned with intuitive individual-level guarantees and extending utility relative to standard differential privacy.
- Scope: The paper also describes an extension to group differential privacy for controllers that want group guarantees while retaining data-dependent distortion.The paper then presents formalization, mechanisms, and accuracy analysis for the proposed notion.
2 Background on Differential Privacy
Differential privacy sanitizes query results by adding noise calibrated to query variability, with global, smooth, and local sensitivity offering different accuracy and privacy trade-offs. Local sensitivity can be much smaller but cannot be used directly in standard DP mechanisms without accounting for neighboring data sets.
- Standard differential privacy: In the interactive setting, a sanitizer replaces f(D) with a randomized approximation whose responses on neighboring data sets are indistinguishable.The privacy parameter ϵ limits each individual's contribution to the query result.
- Composition: Sequential composition adds privacy parameters, while parallel composition preserves ϵ when mechanisms operate on disjoint records or subsets.These composition properties allow multiple private results to be combined with stated privacy accounting.
- Global sensitivity: Global-sensitivity mechanisms calibrate noise to the maximum query variability across neighboring data sets, using distributions such as Laplace noise.The standard numerical mechanism adds independent Laplace noise scaled by ϵ and global sensitivity.
- Local sensitivity: Local sensitivity measures variability around the actual data set and is often much smaller than global sensitivity, potentially improving query accuracy.For the median, local sensitivity is usually 0 except for especially ill-conditioned data sets.
- Local-sensitivity limitation: Using local sensitivity directly in mechanisms designed for global sensitivity does not provide standard differential privacy because neighboring data sets can have different local sensitivities.The median example shows a data set with zero local sensitivity can produce a deterministic result that fails the neighboring-data requirement.
- Smooth sensitivity: Smooth sensitivity accounts for local sensitivities of neighboring data sets, but standard DP then requires heavy-tailed admissible noise distributions.This distributional requirement is a downside of smooth-sensitivity calibration.
3 Related Work
Prior work improves differential-privacy utility through better mechanisms or relaxed privacy definitions. The paper distinguishes its approach by preserving the intuitive individual-level guarantee rather than allowing that condition to be violated.
- Motivation: Differential privacy’s strong guarantees are hindered in practice by poor accuracy, motivating research on mechanisms and relaxations.The paper frames utility limitations as a barrier to practical adoption.
- Accuracy-improving mechanisms: One research line improves accuracy while retaining differential privacy through mechanisms based on smooth sensitivity, optimal noise distributions, microaggregation, dimensionality reduction, and specialized publication methods.These approaches modify mechanisms or exploit structure in the data and query.
- Relaxations: A second research line relaxes differential privacy using approximate, restricted-neighbor, or concentrated definitions.These relaxations alter the privacy condition or the set of neighboring data sets.
- Position of this work: Earlier relaxations obtain accuracy gains by permitting some information leakage about an individual, whereas the proposed relaxation preserves the original individual-level privacy guarantee.The distinction is between weakening the condition and restricting the indistinguishability requirement to the actual data set and its neighbors.
4 Individual differential privacy
The paper argues that standard differential privacy requires indistinguishability between arbitrary neighboring data sets, exceeding the intuitive goal of protecting individuals’ participation. It proposes individual differential privacy, which compares the actual data set with its neighbors and preserves individual guarantees while dropping direct group guarantees.
- Existing differential privacy relaxations may improve utility by weakening privacy, whereas this approach seeks only the intuitive guarantees and nothing more.
- Standard differential privacy requires indistinguishable responses for every pair of neighboring data sets, although queries are answered on the actual data set held by a trusted party.
- Individual differential privacy requires indistinguishability only between the actual data set D and each neighboring data set D′, making the roles of D and D′ asymmetric.
- Any mechanism satisfying ϵ-DP also satisfies ϵ-iDP for every actual data set D, while ϵ-iDP retains strict individual privacy guarantees.
- ϵ-iDP drops direct privacy guarantees for groups, so any group protection is only an indirect consequence of protecting each individual.
- The paper notes that ϵ-iDP satisfies the axioms of transformation invariance and choice.
5 ϵ-iDP for Numerical Queries
For numerical queries, the paper constructs individual differential privacy mechanisms by adding noise calibrated to the actual data set’s local sensitivity. It gives continuous and discrete Laplace mechanisms for numerical outputs.
- The numerical-query mechanism has the form κ(x) = f(x) + N, where f is the query and N is random noise.
- Calibrating noise to local sensitivity LSf(D) enables ϵ-iDP and can improve accuracy over global or smooth sensitivity calibration.The paper also states that local-sensitivity calibration permits exponentially decreasing noise distributions and is simpler than smooth-sensitivity calibration.
- For vector-valued real queries, adding independent Laplace(0, LSf(D)/ϵ) noises gives ϵ-iDP.
- For integer-valued queries, the paper uses discrete noise whose parameter is adjusted to ϵ and the query’s local sensitivity.
- For functions with values in Z^k, independent discrete Laplace noises DL(exp(−ϵ/LSf(D))) produce an ϵ-iDP mechanism.
6 Evaluation
The evaluation compares noise calibrated to global, smooth, and local sensitivity using both simulations and theoretical analysis. It reports that individual differential privacy improves response accuracy even in the worst case.
- The evaluation compares global-sensitivity calibration for standard DP, smooth-sensitivity calibration for standard DP, and local-sensitivity calibration for iDP.
- Because smooth- and local-sensitivity accuracy depends on the actual data set, the paper combines empirical simulations with theoretical analysis.
- Even in the worst case, iDP offers a significant improvement in response accuracy.
6.1 Median
For median queries, individual differential privacy adjusts noise to the actual data set through local sensitivity, avoiding several accuracy and complexity drawbacks of standard differential privacy calibrated to global or smooth sensitivity. The comparison finds substantially tighter noise and better accuracy for iDP under the stated conditions.
- Motivation: The median is relatively insensitive to outliers, but standard DP can still significantly degrade its accuracy because guarantees must hold for every pair of neighboring data sets.iDP instead adjusts protection to each specific data set and therefore usually provides reasonably high accuracy.
- Global and smooth sensitivity: Global sensitivity calibration can severely compromise median accuracy, and unbounded attribute domains may make global sensitivity impossible to compute without artificial restrictions.For the median, global sensitivity can equal the domain size.
- Global and smooth sensitivity: Smooth sensitivity reduces noise for most data sets but requires O(n^2) computation for the median, bounded domains, and more complex mechanisms with heavy-tailed noise.These constraints can limit feasibility and accuracy, especially for large or unbounded data sets.
- Individual differential privacy: Local-sensitivity calibration for iDP is less complex, lower than smooth sensitivity, independent of domain size, and compatible with simpler exponentially decreasing noise such as Laplace noise.For the median, local sensitivity depends only on x_m−1, x_m, and x_m+1.
- Experimental comparison: At 95% confidence, smooth-sensitivity DP noise can reach 101 times the smooth sensitivity, whereas iDP noise is at most 3 times the local sensitivity.The smooth-sensitivity result may be acceptable only when smooth sensitivity is very small relative to the attribute domain.
- Experimental evaluation: The average absolute-error evaluation covers data sets of sizes 10, 100, and 1000 drawn from uniform, normal, and exponential distributions.For the normal and exponential cases, the record domain must be bounded to compute smooth sensitivity.
6.2 Maximum
For maximum queries, global and smooth sensitivity remain tied to the attribute domain, while iDP can reduce this dependence by querying the second maximum.
- The maximum’s global sensitivity equals the domain length, which can severely degrade differentially private estimates.If the domain is unbounded, global sensitivity cannot be computed.
- Smooth sensitivity usually reduces noise relative to global sensitivity but still depends on the attribute domain.It is smaller except for worst-case data sets described in the global-sensitivity analysis.
- iDP uses local sensitivity for the maximum, which is smaller than smooth sensitivity and supports exponentially decreasing noise distributions.The local sensitivity can nevertheless remain domain-dependent when the domain is unbounded.
- Querying the second maximum removes domain dependence from local sensitivity and is reasonably accurate unless one record is a significant outlier.When that exception occurs, maximum-query accuracy is also poor.
- This second-maximum workaround is unavailable when noise is calibrated to smooth sensitivity.
6.3 Range queries
Range and histogram queries already have sensitivity 1 under standard differential privacy, so calibrating iDP noise to local sensitivity does not improve their accuracy.
- A range query counts records within a specified range, and histogram queries collect range queries over disjoint ranges.
- Range queries have sensitivity 1 under differential privacy, and histogram queries preserve this low sensitivity.
- Because local sensitivity also equals 1 for range queries, the described iDP mechanisms provide no accuracy improvement over differential privacy.
7 Conclusions and future work
The paper presents individual differential privacy as a utility-preserving alternative that retains the intuitive individual-level privacy guarantee while reducing noise through data-dependent sensitivity. Its conclusions emphasize improved accuracy, reduced domain dependence, and future extensions beyond the studied interactive numerical setting.
- Individual differential privacy focuses on indistinguishability between the actual data set and its neighbors, reducing query sensitivity and added noise.The paper presents this as preserving the intuitive guarantee that one individual’s presence or absence is unnoticeable.
- For numerical queries, iDP can be attained by calibrating noise to local sensitivity, producing substantial accuracy gains.The paper also notes that directly using differential privacy mechanisms does not realize iDP’s potential accuracy improvements.
- iDP is substantially more accurate because local sensitivity is normally smaller than the global sensitivity used by standard differential privacy.
- Even against smooth-sensitivity calibration, iDP improves accuracy through smaller local sensitivity and exponentially decreasing rather than heavy-tailed noise.
- Local-sensitivity iDP is less dependent on the attribute domain, including domains that are large or unbounded, and permits workarounds when dependence remains.
- The authors argue that iDP’s accuracy gains and individual privacy guarantee could enable use where standard differential privacy is not viable.Future work includes other interactive queries, non-noise mechanisms, non-numerical functions, and non-interactive releases.