Differentially Private Uniformly Most Powerful Tests for Binomial Data

Understand

We derive uniformly most powerful (UMP) tests for simple and one-sided hypotheses for a population proportion within the framework of Differential Privacy (DP), optimizing finite sample performance.

• We show that in general, DP hypothesis tests for exchangeable data can always be expressed as a function of the empirical distribution.
• Using this structure, we prove a `Neyman-Pearson lemma' for binomial data under DP, where the DP-UMP only depends on the sample sum.
• Our tests can also be stated as a post-processing of a random variable, whose distribution we coin "Truncated-Uniform-Laplace" (Tulap), a generalization of the Staircase and discrete Laplace distributions.