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.
Category / Keywords: cryptographic protocols / secure aggregation, multi-party computation Date: received 11 Jun 2020 Contact author: adriag at google com Available format(s): PDF | BibTeX Citation Version: 20200611:234924 (All versions of this report) Short URL: ia.cr/2020/704