论文标题
PAN隐私和洗牌隐私的限制用于学习和估计
The Limits of Pan Privacy and Shuffle Privacy for Learning and Estimation
论文作者
论文摘要
最近，人们对中级信任模型的差异隐私造成了兴趣，这消除了对完全信任的中央数据收集器的需求，但克服了当地差异隐私的局限性。这种兴趣导致了混乱模型的引入（Cheu等人，Eurocrypt 2019; Erlingsson等，Soda 2019）并重新访问了Pan-Private模型（Dwork等，ITCS，2010年）。这项工作的信息是，对于各种低维问题（例如计数，手段和直方图），这些中间模型提供的功率几乎与中央差异隐私一样多。但是，使用这些模型用于高维学习和估计问题的成功率要少得多。在这项工作中，我们表明，对于各种高维学习和估计问题，洗牌模型和泛私有模型都固有地在样本复杂性中相对于中心模型固有地呈指数级。例如，我们表明，这些模型中的私人不属于奇偶校验功能的私人学习功能需要$ω（2^{d/2}）$样本，并且私人从$ d $ choices的集合中私下选择最常见的属性，需要$ω（d^{1/2}）$样本，这两种是从中央模型中均可提供的。我们的工作为这些问题提供了第一个非平凡的下限，用于Pan-Provate模型和一般的多消息混音模型。
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 show that, for a variety of high-dimensional learning and estimation problems, both the shuffle model and the pan-private model inherently incur an exponential price in sample complexity relative to the central model. For example, we show that, private agnostic learning of parity functions over $d$ bits requires $Ω(2^{d/2})$ samples in these models, and privately selecting the most common attribute from a set of $d$ choices requires $Ω(d^{1/2})$ samples, both of which are exponential separations from the central model. Our work gives the first non-trivial lower bounds for these problems for both the pan-private model and the general multi-message shuffle model.
