Reveal-Or-Obscure: a Differentially Private Sampling Algorithm for Discrete Distributions

We introduce a differentially private DP algorithm called reveal-or-obscure ROO to generate a single representative sample from a dataset of $n$ observations drawn i.i.d. from an unknown discrete distribution $P$. Unlike methods that add explicit noise to the estimated empirical distribution, ROO...