Welcome to the resource topic for 2022/920
Title:
Distributed, Private, Sparse Histograms in the Two-Server Model
Authors: James Bell, Adria Gascon, Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Mariana Raykova, and Phillipp Schoppmann
Abstract:We consider the computation of sparse, (\varepsilon, \delta)-differentially private (DP) histograms in the two-server model of secure multi-party computation (MPC), which has recently gained traction in the context of privacy-preserving measurements of aggregate user data. We introduce protocols that enable two semi-honest non-colluding servers to compute histograms over the data held by multiple users, while only learning a private view of the data. Our solution achieves the same asymptotic \ell_\infty-error of O\left(\frac{\log(1/\delta)}{\varepsilon}\right) as in the central model of DP, but \textit{without} relying on a trusted curator. The server communication and computation costs of our protocol are independent of the number of histogram buckets, and are linear in the number of users, while the client cost is independent of the number of users, \varepsilon, and \delta. Its linear dependence on the number of users lets our protocol scale well, which we confirm using microbenchmarks: for a billion users, \varepsilon = 0.5, and \delta = 10^{-11}, the per-user cost of our protocol is only 1.04 ms of server computation and 275 bytes of communication. In contrast, a baseline protocol using garbled circuits only allows up to 10^6 users, where it requires 600 KB communication per user.
ePrint: https://eprint.iacr.org/2022/920
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .