.png){kind=icon}
返回
Optimal Pure Differentially Private Sparse Histograms in Deterministic Linear Time
.png){kind=icon}
PRE
AI
DOI：10.1145/3801909.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们提出了一种算法，可在大小为d >> n的域上为n个参与者释放纯差分私有（在替换邻近关系下）稀疏直方图。我们的方法实现了最优l(infinity)-估计误差，并在Word-RAM模型中以严格O(n)时间运行，改进了之前的最佳确定性时间界~O(n^2)，并解决了打破此二次方壁垒的开放问题（Balcer和Vadhan 2019）。此外，该算法允许高效的电路实现，实现了首个近线性通信和计算成本的纯DP直方图MPC协议，具有最优l(infinity)-估计误差。我们算法的核心是一种新颖的私有项目遮蔽技术，结合目标长度填充，它隐藏了邻近直方图支持集的差异，同时保持高效可实施性。
Keyword:
Differential Privacy
Sparse Histogram
