Distributed Private Data Analysis: On Simultaneously Solving How and What

By Amos Beimel, Kobbi Nissim, Eran Omri. 2008

225 citations recorded by the source corpus.

We examine the combination of two directions in the field of privacy concerning computations over distributed private inputs --- secure function evaluation(SFE) and differential privacy. While in both the goal is to privately evaluate some function of the individual inputs, the privacy requirements are significantly different. The general feasibility results for SFE suggest a natural paradigm for implementing differentially private analyses distributively: First choose whatto compute, i.e., a differentially private analysis; Then decide howto compute it, i.e., construct an SFE protocol for this analysis. We initiate an examination whether there are advantages to a paradigm where both decisions are made simultaneously. In particular, we investigate under which accuracy requirements it is beneficial to adapt this paradigm for computing a collection of functions including Binary Sum, Gap Threshold, and Approximate Median queries. Our results yield new separations between the local and global models of computations for private data analysis.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Privacy & Security

Citations in the corpus

Shuffled Model of Federated Learning: Privacy, Communication and Accuracy Trade-offs (2020, background): “The challenge is that the traditional privacy approach to the learning problem uses local diﬀerential privacy (LDP) [War65, ESAG04, DJW13, BNO08, KLN + 11], which is known to give poor learning performance [DJW13,KLN + 11,KBR16].”
Private Counting from Anonymous Messages: Near-Optimal Accuracy with Vanishing Communication Overhead (2020, background): “For numerous basic tasks, including binary summation and histograms that we study in this work, errors are at least on the order of √ n, where n is the number of users (Beimel et al., 2008; Chan et al., 2012).”
Pure Differentially Private Summation from Anonymous Messages (2020, background): “Nevertheless, the local model suﬀers from large estimation errors that are known to the be on the order of √ n , where n is the number of users, for a variety of problems including summation, the focus of this work [BNO08, CSS12].”
The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “In particular, the number of data points necessary to achieve a particular level of accuracy in the local model is signiﬁcantly larger than what is su ﬃ cient for the same accuracy in the curator model (see, e.g., [10, 43, 56, 9]).”
Inference Under Information Constraints I: Lower Bounds From Chi-Square Contraction (2018, neutral): “[21], [35], [9], [19]): For ρ > 0, W (y | x1) W (y | x2) ≤ e, ∀x1, x2 ∈ [k],∀y ∈ {0, 1}∗.”
Distributed Differential Privacy via Shuffling (2018, neutral): “[4] and Chan et al.”
Extremal Mechanisms for Local Differential Privacy (2014, neutral): “These results follow from our main theorems and are of independent interest in other applications where lower bounds in statistical analysis are studied [3, 21, 6, 9].”
A Hybrid Approach to Privacy-Preserving Federated Learning (2018, background): “[4] provides a theoretical analysis on how differentially private computations could be done in a federated setting for single instance operations using either secure function evaluation or the local model with a semi-trusted curator.”
Separating Local & Shuffled Differential Privacy via Histograms (2019, background): “In contrast, [5] gives a lower bound of Ω(1/α2ε2) in the local model.”
Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation (2013, background): “[2, 16, 8]): prior work focuses on accurate estimation of a samplequantityθ(x1:n) based on the samplex1:n, while we provide lower bounds on error of the populationestimatorθ(P ).”
Differentially private combinatorial optimization (2009, background): “[10, 5]), in the absence of a trusted curator.”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “A popular privacy definition is local differential privacy (LDP), which was perhaps first proposed in (Warner, 1965), and more recently in (Beimel et al., 2008; Kasiviswanathan et al., 2011), where users do not trust the data collector, and privatize their data before releasing.”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, background): “The basic diﬀerential privacy framework is the foundation for many models, including central [18], local [18, 11, 28], pan-[19], blended [6], and most recently shuﬄe [16] privacy.”
Private Nearest Neighbors Classification in Federated Databases (2018, methodology): “This leads to the definition of multi-party computationally differential privacy which has been studied by Dwork et al. (2006a); Beimel et al. (2008).”