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. Unlike methods that add explicit noise to the estimated empirical distribution, ROO achieves ϵ - differential privacy by randomly choosing whether to "reveal" or "obscure" the empirical distribution. While ROO is structurally identical to Algorithm 1 proposed by Cheu and Nayak [1], we prove a strictly better bound on the sampling complexity than that extablished in Theorem 12 of [1]. T o further improve the privacy-utility trade-off, we propose a novel generalized sampling algorithm called Data-Specific ROO (DS-ROO), where the probability of obscuring the empirical distribution of the dataset is chosen adaptively. We prove that DS-ROO satisfies ϵ - DP, and provide empirical evidence that DS-ROO can achieve better utility under the same privacy budget of vanilla ROO. The widespread use of sensitive data across various domains, including healthcare, finance, law enforcement, and social sciences, has heightened the importance of privacy-preserving data analysis.