论文标题
通过投影几何形状估算私人频率
Private Frequency Estimation via Projective Geometry
论文作者
论文摘要
在这项工作中，我们提出了一种针对本地差异私有（LDP）频率估计的新算法投影型射击测量值（PGR）。对于$ k $的宇宙尺寸和$ n $用户，我们的$ \ varepsilon $ -LDP算法的通信成本$ \ lceil \ lce_2k \ log_2k \ rceil $ bits in Private Coin设置中的bits bits $ \ varepsilon \ varepsilon \ varepsilon \ log_2 e + o（log_2 e + o（1）$ in Public coin设置和compul coin设置和compul coin coin nov $ o（n + o（n + o） k）$ for Server大致重建频率直方图，同时实现最先进的隐私性 - 实用性权衡。在实践中使用的许多参数设置中，这比最近的PI-Rappor算法（Feldman and Talwar; 2021）实现了$ O（N+K^2）$计算成本的重大改进。我们的经验评估表明，超过50倍超过Pi-cappor的加速度，同时使用大约75倍的内存来进行实际相关的参数设置。此外，我们算法的运行时间在Hadamardresponse（Acharya，Sun和Zhang; 2019）和RecursiveHadamardResponse（Chen，Kairouz和Ozgur; 2020）之内。我们的算法的误差基本上与通信和时间无关但效用 - 最佳的子选择（SS）算法相匹配（Ye and Barg; 2017）。我们的新算法基于在有限字段上使用投影平面来定义一小部分集合，这些集合接近成对独立和动态编程算法，用于服务器端上的近似直方图重建。我们还提供了PGR的扩展，我们称之为HybridprojectiveGeometryResponse，可以通过实用程序顺畅地交换计算时间。
In this work, we propose a new algorithm ProjectiveGeometryResponse (PGR) for locally differentially private (LDP) frequency estimation. For a universe size of $k$ and with $n$ users, our $\varepsilon$-LDP algorithm has communication cost $\lceil\log_2k\rceil$ bits in the private coin setting and $\varepsilon\log_2 e + O(1)$ in the public coin setting, and has computation cost $O(n + k\exp(\varepsilon) \log k)$ for the server to approximately reconstruct the frequency histogram, while achieving the state-of-the-art privacy-utility tradeoff. In many parameter settings used in practice this is a significant improvement over the $ O(n+k^2)$ computation cost that is achieved by the recent PI-RAPPOR algorithm (Feldman and Talwar; 2021). Our empirical evaluation shows a speedup of over 50x over PI-RAPPOR while using approximately 75x less memory for practically relevant parameter settings. In addition, the running time of our algorithm is within an order of magnitude of HadamardResponse (Acharya, Sun, and Zhang; 2019) and RecursiveHadamardResponse (Chen, Kairouz, and Ozgur; 2020) which have significantly worse reconstruction error. The error of our algorithm essentially matches that of the communication- and time-inefficient but utility-optimal SubsetSelection (SS) algorithm (Ye and Barg; 2017). Our new algorithm is based on using Projective Planes over a finite field to define a small collection of sets that are close to being pairwise independent and a dynamic programming algorithm for approximate histogram reconstruction on the server side. We also give an extension of PGR, which we call HybridProjectiveGeometryResponse, that allows trading off computation time with utility smoothly.
