Extremal Mechanisms for Local Differential Privacy

By Peter Kairouz, Sewoong Oh, Pramod Viswanath. 2014

667 citations recorded by the source corpus.

Local differential privacy has recently surfaced as a strong measure of privacy in contexts where personal information remains private even from data analysts. Working in a setting where the data providers and data analysts want to maximize the utility of statistical inferences performed on the released data, we study the fundamental tradeoff between local differential privacy and information theoretic utility functions. We introduce a family of extremal privatization mechanisms, which we call staircase mechanisms, and prove that it contains the optimal privatization mechanism that maximizes utility. We further show that for all information theoretic utility functions studied in this paper, maximizing utility is equivalent to solving a linear program, the outcome of which is the optimal staircase mechanism. However, solving this linear program can be computationally expensive since it has a number of variables that is exponential in the data size. To account for this, we show that two simple staircase mechanisms, the binary and randomized response mechanisms, are universally optimal in the high and low privacy regimes, respectively, and well approximate the intermediate regime.

Subfields: Artificial Intelligence, Sociology and Political Science, 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 Sociology and Political Science

In Privacy & Security

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “While LDP protocols are effective at enforcing privacy and have theoretical justifications [156, 135, 136], a number of results have shown that achieving local differential privacy while preserving utility is challenging particularly, especially in high-dimensional data settings [229, 388, 219, 51, ”
Privacy Amplification by Decentralization (2020, methodology): “For this problem, a classic approach in LDP is L-ary randomized response [24], where a user submits its true value with probability 1− γ and a uniformly random value with probability γ.”
Breaking the Communication-Privacy-Accuracy Trilemma (2020, methodology): “1) The 1-bit Case: In this case, each client transmits a uniformly at random chosen entry of Yi via any 1-bit LDP channel (for instance, using the 2-randomized response (RR) scheme [3], [43], [52]).”
The Privacy Blanket of the Shuffle Model (2019, methodology): “This randomizer has been studied and used (in the local model) in several previous works [21, 20, 7].”
Federated Heavy Hitters Discovery with Differential Privacy (2019, background): “…of fundamental work shows that in the context of learning distributions and heavy hitters, local DP often leads to a signiﬁcant reduction in utility (Kairouz et al., 2014; Wang et al., 2017; Bassily et al., 2017; Kairouz et al., 2016; Ye and Barg, 2018; Duchi et al., 2013; Cormode et al., 2018).”
The Power of the Hybrid Model for Mean Estimation (2018, background): “However, it is well understood theoretically and empirically that utility outcomes are far worse in the LM than in the TCM [11, 16, 22, 27, 38].”
Differentially-Private "Draw and Discard" Machine Learning (2018, background): “There are also numerous results on the so-called sample complexity for the local model, showing that the number of data points needed to achieve comparable accuracy is signiﬁcantly higher in the local model than in the trusted curator model [28].”
Marginal Release Under Local Differential Privacy (2017, background): “The ﬁrst extension of RR is a natural generalization also proposed e.g. by [23], which we call Preferential Sampling.”
Personalized and Private Peer-to-Peer Machine Learning (2017, background): “local DP (Duchi et al., 2012; Kairouz et al., 2016), leads to very inaccurate models.”
BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, background): “Furthermore, the utility of the resulting data obtained through these algorithms is significantly limited compared to what is possible in the trusted curator model, as shown experimentally [15, 21] and theoretically [22].”
Optimal Schemes for Discrete Distribution Estimation Under Locally Differential Privacy (2017, background): “In this part we are motivated by a result in [11] which shows that a similar property holds for schemes optimal in terms of information theoretic utilities, such as mutual information between the input and the output.”
Discrete Distribution Estimation under Local Privacy (2016, methodology): “(Kairouz et al., 2014) introduced k-RR and showed that it is optimal in the low privacy regime for a rich class of information theoretic utility functions.”
Collecting and Analyzing Multidimensional Data with Local Differential Privacy (2019, background): “[24] propose the extremal mechanisms, which are a family of LDP mechanisms for data with discrete inputs, i.”
Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries (2015, background): “Research on local differential privacy has largely been centered around finding algorithms that satisfy differential privacy properties [19, 21, 22], and improving the tradeoffs between privacy and utility [7, 14].”
Encode, Shuffle, Analyze Privacy Revisited: Formalizations and Empirical Evaluation (2020, background): “Algorithm 1 shows how to (naturally) apply attribute fragmenting when the local randomizer R is what is referred to as the k -RAPPOR randomizer [35].”
PacGAN: The Power of Two Samples in Generative Adversarial Networks (2017, methodology): “This was used to prove strong composition theorems in differential privacy [34] and to identify the optimal differentially-private mechanisms under local privacy [32] and multi-party communications [33].”