一种新型差分隐私采样算法，通过随机揭示或隐藏数据分布来保护隐私。
Reveal-or-Obscure: A Differentially Private Sampling Algorithm for Discrete Distributions
- 通过随机选择揭示或隐藏经验分布实现差分隐私
- 采样复杂度优于已有方法，理论边界更优
- 自适应调整隐藏概率，提升隐私与效用平衡
我们提出一种名为揭示或隐藏（Reveal-or-Obscure, ROO）的差分隐私（DP）算法，用于从独立同分布的n个观测值构成的数据集中生成单一代表性样本。该算法不向经验分布添加显式噪声，而是通过随机决定是否‘揭示’或‘隐藏’经验分布来实现ε-差分隐私。尽管结构与Cheu和Nayak（arXiv:2412.10512）提出的算法1相同，但我们证明了其采样复杂度的界比该文献第12定理中的结果更紧。为进一步优化隐私-效用权衡，我们提出一种新型泛化采样算法——数据特定揭示或隐藏（DS-ROO），其中数据集的隐藏概率可自适应选择。我们证明了DS-ROO满足ε-差分隐私，并通过实验验证其在相同隐私预算下相比原版ROO具有更高效用。
原文摘要 · Abstract (English)
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 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 (arXiv:2412.10512), we prove a strictly better bound on the sampling complexity than that established in Theorem 12 of (arXiv:2412.10512). To 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。