Paper 2022/920

Distributed, Private, Sparse Histograms in the Two-Server Model

James Bell, Google
Adria Gascon, Google
Badih Ghazi, Google
Ravi Kumar, Google
Pasin Manurangsi, Google
Mariana Raykova, Google
Phillipp Schoppmann, Google

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 \emph{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.08$ ms of server computation and $339$ 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2022
Multi-Party Computation Differential Privacy Histograms
Contact author(s)
jhbell @ google com
adriag @ google com
badihghazi @ google com
tintin @ google com
pasin @ google com
marianar @ google com
schoppmann @ google com
2022-09-08: revised
2022-07-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {James Bell and Adria Gascon and Badih Ghazi and Ravi Kumar and Pasin Manurangsi and Mariana Raykova and Phillipp Schoppmann},
      title = {Distributed, Private, Sparse Histograms in the Two-Server Model},
      howpublished = {Cryptology ePrint Archive, Paper 2022/920},
      year = {2022},
      doi = {10.1145/3548606.3559383},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.