The Role of Interactivity in Local Differential Privacy

By Matthew Joseph, Jieming Mao, Seth Neel, Aaron Roth. 2019

74 citations recorded by the source corpus.

We study the power of interactivity in local differential privacy. First, we focus on the difference between fully interactive and sequentially interactive protocols. Sequentially interactive protocols may query users adaptively in sequence, but they cannot return to previously queried users. The vast majority of existing lower bounds for local differential privacy apply only to sequentially interactive protocols, and before this paper it was not known whether fully interactive protocols were more powerful. We resolve this question. First, we classify locally private protocols by their compositionality, the multiplicative factor by which the sum of a protocol's single-round privacy parameters exceeds its overall privacy guarantee. We then show how to efficiently transform any fully interactive compositional protocol into an equivalent sequentially interactive protocol with a blowup in sample complexity linear in this compositionality. Next, we show that our reduction is tight by exhibiting a family of problems such that any sequentially interactive protocol requires this blowup in sample complexity over a fully interactive compositional protocol. We then turn our attention to hypothesis testing problems. We show that for a large class of compound hypothesis testing problems --- which include all simple hypothesis testing problems as a special case --- a simple noninteractive test is optimal among the class of all (possibly fully interactive) tests.

Subfields: Artificial Intelligence, Computer Science Applications

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 Computer Science Applications

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, background): “The adoption of the local model by major industry players has motivated a line of research in the theory of local di ﬀ erential privacy (e.g., [9, 8, 16, 59, 40, 42, 41]).”
The Privacy Blanket of the Shuffle Model (2019, methodology): “[19] already used a generalization of our blanket decomposition in their study of the role of interactivity in local DP protocols.”
Separating Local & Shuffled Differential Privacy via Histograms (2019, background): “But [15] gives a lower bound of Ω(h3/(ε2 log h)) in the local model when s = h4, even allowing for sequential interactivity.”
Lower Bounds for Locally Private Estimation via Communication Complexity (2019, background): “This limits the interaction between private communications, and there are problems for which fully interactive mechanisms are more powerful than compositional ones (Joseph et al., 2019).”
Locally Private Gaussian Estimation (2018, background): “[16] appears in the full version of this paper [15].”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “[36] also considers the role of interactivity in LDP hypothesis testing; however, they focus on simple hypothesis testing (as well as a generalization to convex hypothesis classes).”
Pan-Private Uniformity Testing (2019, background): “Up to this diﬀerence, our local diﬀerential privacy deﬁnitions generally imitate those given by Joseph et al. [30].. Deﬁnition 3.”