The limits of pan privacy and shuffle privacy for learning and estimation
The limits of pan privacy and shuffle privacy for learning and estimation
复制标题
DOI：
10.1145/3406325.3450995
复制
发表时间：
2020-09
期刊：
影响因子：
--
通讯作者：
Albert Cheu;Jonathan Ullman
中科院分区：
文献类型：
--
作者：
Albert Cheu;Jonathan Ullman
最近出现了一波对用于差分隐私的中间信任模型的兴趣，该模型消除了对完全可信的中央数据收集器的需要，但克服了局部差分隐私的限制。这种兴趣导致了洗牌模型的引入（Cheu等人，EUROPENTER PT 2019; Erlingsson等人，SODA 2019）和重新审视泛私有模式（Dwork等人，ITCS 2010）。这一系列工作的信息是，对于各种低维问题，如计数，均值和直方图，这些中间模型提供了几乎与中央差分隐私一样多的权力。然而，有相当少的成功使用这些模型的高维学习和估计问题。在这项工作中，我们证明了第一个非平凡的高维学习和估计的泛私人模型和一般的多消息洗牌模型的下界。我们的下界适用于各种问题，例如，我们表明，在这些模型中，d位奇偶函数的私人不可知学习需要Ω（2d/2）个样本，而从一组d个选择中私人选择最常见的属性需要Ω（d1/2）个样本，这两个样本都是中心模型的指数分离。
There has been a recent wave of interest in intermediate trust models for differential privacy that eliminate the need for a fully trusted central data collector, but overcome the limitations of local differential privacy. This interest has led to the introduction of the shuffle model (Cheu et al., EUROCRYPT 2019; Erlingsson et al., SODA 2019) and revisiting the pan-private model (Dwork et al., ITCS 2010). The message of this line of work is that, for a variety of low-dimensional problems—such as counts, means, and histograms—these intermediate models offer nearly as much power as central differential privacy. However, there has been considerably less success using these models for high-dimensional learning and estimation problems. In this work we prove the first non-trivial lower bounds for high-dimensional learning and estimation in both the pan-private model and the general multi-message shuffle model. Our lower bounds apply to a variety of problems—for example, we show that, private agnostic learning of parity functions over d bits requires Ω(2d/2) samples in these models, and privately selecting the most common attribute from a set of d choices requires Ω(d1/2) samples, both of which are exponential separations from the central model.