Smoothed Differential Privacy
Preprint
Abstract
Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. Often, DP classifies most mechanisms without additive noise as non-private (Dwork et al., 2014). Thus, additive noises are added to improve privacy (to achieve DP). However, in many real-world applications, adding additive noise is undesirable (Bagdasaryan et al., 2019) and sometimes prohibited (Liu et al., 2020). In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis (Spielman & Teng, May 2004). Our notion, smoothed DP, can effectively measure the privacy leakage of mechanisms without additive noises under realistic settings. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP. In addition, we prove several desirable properties of smoothed DP, including composition, robustness to post-processing, and distribution reduction. Based on those properties, we propose an efficient algorithm to calculate the privacy parameters for smoothed DP. Experimentally, we verify that, according to smoothed DP, the discrete sampling mechanisms are private in real-world elections, and some discrete neural networks can be private without adding any additive noise. We believe that these results contribute to the theoretical foundation of realistic privacy measures beyond worst-case analysis.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Comparing approximate and probabilistic differential privacy parametersInformation Processing Letters, 2023
- Adversarially Robust Streaming Algorithms via Differential PrivacyJournal of the ACM, 2022
- Certifiably robust interpretation via Rényi differential privacyArtificial Intelligence, 2022
- High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge LearningIEEE Transactions on Signal Processing, 2020
- Privacy Enhanced Matrix Factorization for Recommendation with Local Differential PrivacyIEEE Transactions on Knowledge and Data Engineering, 2018
- The Algorithmic Foundations of Differential Privacy2013
- A Statistical Framework for Differential PrivacyJournal of the American Statistical Association, 2010
- Fast neural networks without multipliersIEEE Transactions on Neural Networks, 1993
- Weight quantization in Boltzmann machinesNeural Networks, 1991
- Weight discretization paradigm for optical neural networks1990