Welcome to the resource topic for 2024/469
Title:
Malicious Security for Sparse Private Histograms
Authors: Lennart Braun, Adrià Gascón, Mariana Raykova, Phillipp Schoppmann, Karn Seth
Abstract: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.
ePrint: https://eprint.iacr.org/2024/469
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 .