The limits of pan privacy and shuffle privacy for learning and estimation

By Albert Cheu, Jonathan Ullman. 2020

26 citations recorded by the source corpus.

There has been a recent wave of interest in intermediate trust models for differential privacy that eliminate the need for a fully trusted central data collector, but overcome the limitations of local differential privacy. This interest has led to the introduction of the shuffle model (Cheu et al., EUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private model (Dwork et al., ITCS 2010). The message of this line of work is that, for a variety of low-dimensional problems—such as counts, means, and histograms—these intermediate models offer nearly as much power as central differential privacy. However, there has been considerably less success using these models for high-dimensional learning and estimation problems. In this work we prove the first non-trivial lower bounds for high-dimensional learning and estimation in both the pan-private model and the general multi-message shuffle model. Our lower bounds apply to a variety of problems—for example, we show that, private agnostic learning of parity functions over d bits requires Ω(2d/2) samples in these models, and privately selecting the most common attribute from a set of d choices requires Ω(d1/2) samples, both of which are exponential separations from the central model.

Subfields: Artificial Intelligence

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

Citations in the corpus

On Distributed Differential Privacy and Counting Distinct Elements (2020, background): “In a recent concurrent work, Cheu and Ullman [13] proved that robust DP shuﬄe protocols solving Selection and ParityLearning require Ω( √ D ) and Ω(2 √ ) samples, respectively.”
Private Hypothesis Selection (2019, background): “Under various notions of pan-privacy [89] and the shuffled model [90], [91], which are intermediate to local and central differential privacy, the sample complexity of m-wise simple hypothesis testing (the easier version of hypothesis selection, where the unknown distribution is equal to one of the ”
When is memorization of irrelevant training data necessary for high-accuracy learning? (2020, background): “6 in Cheu and Ullman [14] for such a proof; one first shows that any one-sample (α, β)DP algorithm can be converted into a one-sample (2α, 0)-DP algorithm that is close in total variation distance.”
On the Round Complexity of the Shuffle Model (2020, background): “Independent and parallel to our work, Cheu and Ullman [15] presented exponential separations between the 1-round shuffle model and the (centralized) curator model of differential privacy.”