Processing math: 100%

amin20a@v125@PMLR

Total: 1

#1 Pan-Private Uniformity Testing [PDF] [Copy] [Kimi] [REL]

Authors: Kareem Amin, Matthew Joseph, Jieming Mao

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 \emph{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.

Subject: COLT.2020 - Accept