论文标题
连续改进隐私
Successive Refinement of Privacy
论文作者
论文摘要
这项工作研究了一个新的问题：实现当地差异隐私（LDP）需要多少随机性？一个激励的方案是使用\ emph {same}（随机）输出向多个分析师提供{\ em多个级别的隐私}。我们称此设置为\ emph {连续的隐私改进}，因为它提供了对具有不同隐私级别的原始数据的层次结构访问。例如，相同的随机输出可以使一位分析师能够重建输入，而另一个分析师只能估算出符合LDP要求的分配。这将经典的香农（Wiletap）安全设置扩展到了当地的微分隐私。在几种情况下，我们提供了（订单）的（订单）严格特征，以进行分发估算，包括在随机性约束下的标准LDP设置。我们还为多层隐私提供了一种非平凡的隐私机制。此外，我们表明，在保留每个用户的隐私的同时，我们无法随机重复使用随机键。
This work examines a novel question: how much randomness is needed to achieve local differential privacy (LDP)? A motivating scenario is providing {\em multiple levels of privacy} to multiple analysts, either for distribution or for heavy-hitter estimation, using the \emph{same} (randomized) output. We call this setting \emph{successive refinement of privacy}, as it provides hierarchical access to the raw data with different privacy levels. For example, the same randomized output could enable one analyst to reconstruct the input, while another can only estimate the distribution subject to LDP requirements. This extends the classical Shannon (wiretap) security setting to local differential privacy. We provide (order-wise) tight characterizations of privacy-utility-randomness trade-offs in several cases for distribution estimation, including the standard LDP setting under a randomness constraint. We also provide a non-trivial privacy mechanism for multi-level privacy. Furthermore, we show that we cannot reuse random keys over time while preserving privacy of each user.
