Timezone: »
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 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 Θ(√k), while noninteractive locally private uniformity testing has sample complexity Θ(k). We show that the sample complexity of pan-private uniformity testing is Θ(k2/3). By a new Ω(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.
Author Information
Kareem Amin (Google Research)
Matthew Joseph (University of Pennsylvania)
More from the Same Authors
-
2021 Poster: Learning with Labeling Induced Abstentions »
Kareem Amin · Giulia DeSalvo · Afshin Rostamizadeh -
2021 Poster: Learning with User-Level Privacy »
Daniel Levy · Ziteng Sun · Kareem Amin · Satyen Kale · Alex Kulesza · Mehryar Mohri · Ananda Theertha Suresh -
2019 Poster: Differentially Private Covariance Estimation »
Kareem Amin · Travis Dick · Alex Kulesza · Andres Munoz Medina · Sergei Vassilvitskii -
2018 Poster: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2018 Spotlight: Local Differential Privacy for Evolving Data »
Matthew Joseph · Aaron Roth · Jonathan Ullman · Bo Waggoner -
2017 Poster: Repeated Inverse Reinforcement Learning »
Kareem Amin · Nan Jiang · Satinder Singh -
2017 Spotlight: Repeated Inverse Reinforcement Learning »
Kareem Amin · Nan Jiang · Satinder Singh