Jump to Content

Pan-Private Uniformity Testing

Kareem Amin
Jieming Mao
(2020)

Abstract

A differentially private algorithm guarantees privacy against an adversary that sees the output of the algorithm. We study pan-privacy, which guarantees privacy against an adversary that sees both the output and any single internal state of the algorithm during its computation. First, we motivate the single-intrusion assumption by showing that pan-privacy against multiple intrusions is equivalent to sequentially interactive local privacy. Next, we contextualize pan-privacy by analyzing the sample complexity of uniformity testing. We show that this sample complexity sits strictly between that of the central and (sequentially interactive) local models.