Google Research

Pan-Private Uniformity Testing

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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work