[Resource Topic] 2020/704: Secure Single-Server Aggregation with (Poly)Logarithmic Overhead

Welcome to the resource topic for 2020/704

Title:
Secure Single-Server Aggregation with (Poly)Logarithmic Overhead

Authors: James Bell, K. A. Bonawitz, Adrià Gascón, Tancrède Lepoint, Mariana Raykova

Abstract:

Secure aggregation is a cryptographic primitive that enables a server to learn the sum of the vector inputs of many clients. Bonawitz et al. (CCS 2017) presented a construction that incurs computation and communication for each client linear in the number of parties. While this functionality enables a broad range of privacy preserving computational tasks, scaling concerns limit its scope of use. We present the first constructions for secure aggregation that achieve polylogarithmic communication and computation per client. Our constructions provide security in the semi-honest and the semi-malicious setting where the adversary controls the server and a \gamma-fraction of the clients, and correctness with up to \delta-fraction dropouts among the clients. Our constructions show how to replace the complete communication graph of Bonawitz et al., which entails the linear overheads, with a k-regular graph of logarithmic degree while maintaining the security guarantees. Beyond improving the known asymptotics for secure aggregation, our constructions also achieve very efficient concrete parameters. The semi-honest secure aggregation can handle a billion clients at the per client cost of the protocol of Bonawitz et al. for a thousand clients. In the semi-malicious setting with 10^4 clients, each client needs to communicate only with 3\% of the clients to have a guarantee that its input has been added together with the inputs of at least 5000 other clients, while withstanding up to 5\% corrupt clients and 5\% dropouts. We also show an application of secure aggregation to the task of secure shuffling which enables the first cryptographically secure instantiation of the shuffle model of differential privacy.

ePrint: https://eprint.iacr.org/2020/704

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 .