Paper 2024/469

Malicious Security for Sparse Private Histograms

Lennart Braun, Aarhus University
Adrià Gascón, Google (United States)
Mariana Raykova, Google (United States)
Phillipp Schoppmann, Google (United States)
Karn Seth, Google (United States)

We present a construction for secure computation of differentially private sparse histograms that aggregates the inputs from a large number of clients. Each client contributes a value to the aggregate at a specific index. We focus on the case where the set of possible indices is superpolynomially large. Hence, the resulting histogram will be sparse, i.e., most entries will have the value zero. Our construction relies on two non-colluding servers and provides security against malicious adversaries that may control one of the servers and any numbers of clients. It achieves communication and computation complexities linear in the input size, and achieves the optimal error $O\big(\frac{\log(1/\delta)}{\epsilon}\big)$, independent of the size of the domain of indices. We compute the communication cost of our protocol, showing its scalability. For a billion clients, the communication cost for each server is under 26 KiB per client. Our paper solves an open problem of the work of Bell et al. (CCS'22) which presented a solution for the semi-honest setting while incurring sublinear overhead in its efficiency. We formalize a proof approach for proving malicious security in settings where the output and possible additional information revealed during the execution need to provide differential privacy.

Available format(s)
Cryptographic protocols
Publication info
multiparty computationhistogramsdifferential privacyaggregation
Contact author(s)
braun @ cs au dk
adriag @ google com
marianar @ google com
schoppmann @ google com
karn @ google com
2024-03-22: approved
2024-03-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Lennart Braun and Adrià Gascón and Mariana Raykova and Phillipp Schoppmann and Karn Seth},
      title = {Malicious Security for Sparse Private Histograms},
      howpublished = {Cryptology ePrint Archive, Paper 2024/469},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.