More Like this

1. A Central Limit Theorem for Differentially Private Query Answering

   Jinshuo Dong; Weijie J Su; Linjun Zhang (January 2021, Neural Information Processing Systems (NeurIPS))

   Perhaps the single most important use case for differential privacy is to privately answer numerical queries, which is usually achieved by adding noise to the answer vector. The central question, therefore, is to understand which noise distribution optimizes the privacy-accuracy trade-off, especially when the dimension of the answer vector is high. Accordingly, extensive literature has been dedicated to the question and the upper and lower bounds have been matched up to constant factors [BUV18, SU17]. In this paper, we take a novel approach to address this important optimality question. We first demonstrate an intriguing central limit theorem phenomenon in the high-dimensional regime. More precisely, we prove that a mechanism is approximately Gaussian Differentially Private [DRS21] if the added noise satisfies certain conditions. In particular, densities proportional to e−∥x∥αp, where ∥x∥p is the standard ℓp-norm, satisfies the conditions. Taking this perspective, we make use of the Cramer--Rao inequality and show an "uncertainty principle"-style result: the product of the privacy parameter and the ℓ2-loss of the mechanism is lower bounded by the dimension. Furthermore, the Gaussian mechanism achieves the constant-sharp optimal privacy-accuracy trade-off among all such noises. Our findings are corroborated by numerical experiments. 

   more » « less
2. Central Limit Theorem and Uncertainty Principles for Differentially Private Query Answering

   Jinshuo Dong, Weijie Su (January 2021, Advances in neural information processing systems)

   Perhaps the single most important use case for differential privacy is to privately answer numerical queries, which is usually achieved by adding noise to the answer vector. The central question is, therefore, to understand which noise distribution optimizes the privacy-accuracy trade-off, especially when the dimension of the answer vector is high. Accordingly, an extensive literature has been dedicated to the question and the upper and lower bounds have been successfully matched up to constant factors (Bun et al.,2018; Steinke & Ullman, 2017). In this paper, we take a novel approach to address this important optimality question. We first demonstrate an intriguing central limit theorem phenomenon in the high-dimensional regime. More precisely, we prove that a mechanism is approximately Gaussian Differentially Private (Dong et al., 2021) if the added noise satisfies certain conditions. In particular, densities proportional to exp(-||x||_p^alpha), where ||x||_p is the standard l_p-norm, satisfies the conditions. Taking this perspective, we make use of the Cramer--Rao inequality and show an "uncertainty principle"-style result: the product of privacy parameter and the l_2-loss of the mechanism is lower bounded by the dimension. Furthermore, the Gaussian mechanism achieves the constant-sharp optimal privacy-accuracy trade-off among all such noises. Our findings are corroborated by numerical experiments. 

   more » « less
3. Privacy-Aware Randomized Quantization via Linear Programming

   Cai, Zhongteng; Zhang, Xueru; Khalili, Mohammad_Mahdi (April 2024, https://openreview.net/forum?id=vWsf4L7rHq)

   Differential privacy mechanisms such as the Gaussian or Laplace mechanism have been widely used in data analytics for preserving individual privacy. However, they are mostly designed for continuous outputs and are unsuitable for scenarios where discrete values are necessary. Although various quantization mechanisms were proposed recently to generate discrete outputs under differential privacy, the outcomes are either biased or have an inferior accuracy-privacy trade-off. In this paper, we propose a family of quantization mechanisms that is unbiased and differentially private. It has a high degree of freedom and we show that some existing mechanisms can be considered as special cases of ours. To find the optimal mechanism, we formulate a linear optimization that can be solved efficiently using linear programming tools. Experiments show that our proposed mechanism can attain a better privacy-accuracy trade-off compared to baselines. 

   more » « less
4. Optimizing fitness-for-use of differentially private linear queries

   https://doi.org/10.14778/3467861.3467864  

   Xiao, Yingtai; Ding, Zeyu; Wang, Yuxin; Zhang, Danfeng; Kifer, Daniel (June 2021, Proceedings of the VLDB Endowment)

   null (Ed.)

   In practice, differentially private data releases are designed to support a variety of applications. A data release is fit for use if it meets target accuracy requirements for each application. In this paper, we consider the problem of answering linear queries under differential privacy subject to per-query accuracy constraints. Existing practical frameworks like the matrix mechanism do not provide such fine-grained control (they optimize total error, which allows some query answers to be more accurate than necessary, at the expense of other queries that become no longer useful). Thus, we design a fitness-for-use strategy that adds privacy-preserving Gaussian noise to query answers. The covariance structure of the noise is optimized to meet the fine-grained accuracy requirements while minimizing the cost to privacy. 

   more » « less
5. Node and Edge Differential Privacy for Graph Laplacian Spectra: Mechanisms and Scaling Laws

   https://doi.org/10.1109/TNSE.2023.3329379  

   Hawkins, Calvin; Chen, Bo; Yazdani, Kasra; Hale, Matthew (March 2024, IEEE Transactions on Network Science and Engineering)

   This paper develops a framework for privatizing the spectrum of the Laplacian of an undirected graph using differential privacy. We consider two privacy formulations. The first obfuscates the presence of edges in the graph and the second obfuscates the presence of nodes. We compare these two privacy formulations and show that the privacy formulation that considers edges is better suited to most engineering applications. We use the bounded Laplace mechanism to provide (epsilon, delta)-differential privacy to the eigenvalues of a graph Laplacian, and we pay special attention to the algebraic connectivity, which is the Laplacian's the second smallest eigenvalue. Analytical bounds are presented on the accuracy of the mechanisms and on certain graph properties computed with private spectra. A suite of numerical examples confirms the accuracy of private spectra in practice. 

   more » « less