Pan-Private Uniformity Testing

By Kareem Amin, Matthew Joseph, Jieming Mao. 2019

25 citations recorded by the source corpus.

A centrally differentially private algorithm maps raw data to differentially private outputs. In contrast, a locally differentially private algorithm may only access data through public interaction with data holders, and this interaction must be a differentially private function of the data. We study the intermediate model of pan-privacy. Unlike a locally private algorithm, a pan-private algorithm receives data in the clear. Unlike a centrally private algorithm, the algorithm receives data one element at a time and must maintain a differentially private internal state while processing this stream. First, we show that pure pan-privacy against multiple intrusions on the internal state is equivalent to sequentially interactive local privacy. Next, we contextualize pan-privacy against a single intrusion by analyzing the sample complexity of uniformity testing over domain $[k]$. Focusing on the dependence on $k$, centrally private uniformity testing has sample complexity $\Theta(\sqrt{k})$, while noninteractive locally private uniformity testing has sample complexity $\Theta(k)$. We show that the sample complexity of pure pan-private uniformity testing is $\Theta(k^{2/3})$. By a new $\Omega(k)$ lower bound for the sequentially interactive setting, we also separate pan-private from sequentially interactive locally private and multi-intrusion pan-private uniformity testing.

How researchers see this paper

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

Citations in the corpus

Privacy Amplification by Decentralization (2020, background): “Other recent work has studied the relation between pan-privacy with several breaches and the local model (Amin et al., 2019).”
Connecting Robust Shuffle Privacy and Pan-Privacy (2020, methodology): “[5] (itself a generalization of a similar technique from Acharya et al.”
Descent-to-Delete: Gradient-Based Methods for Machine Unlearning (2020, background): “(2010); Amin et al. (2019)) which also requires that the internal state satisfy statistical indistinguishability. We remark that while unlearning algorithms that are allowed to maintain a “secret state” that need not satisfy the data deletion notion require additional trust in the security of the tr”
Inference Under Information Constraints III: Local Privacy Constraints (2021, methodology): “References [5], [12], [17] consider identity testing using sequentially interactive schemes, which combined with our results prove that interactivity cannot lead to an improvement in the sample complexity over public-coin noninteractive schemes.”
The limits of pan privacy and shuffle privacy for learning and estimation (2020, background): “For simplicity, we will restrict this discussion to pan-private algorithms, as lower bounds for shuffle privacy will then follow from a general transformation from the shuffle model to the pan-privacy model due to Balcer, Cheu, Joseph, and Mao [3].”