Paper 2020/704

Secure Single-Server Aggregation with (Poly)Logarithmic Overhead

James Bell, K. A. Bonawitz, Adrià Gascón, Tancrède Lepoint, and 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. MAJOR revision.2020 ACM SIGSAC Conference on Computer and Communications Security (CCS '20)
DOI
10.1145/3372297.3417885
Keywords
secure aggregationmulti-party computation
Contact author(s)
adriag @ google com
History
2020-11-10: last of 2 revisions
2020-06-11: received
See all versions
Short URL
https://ia.cr/2020/704
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/704,
      author = {James Bell and K.  A.  Bonawitz and Adrià Gascón and Tancrède Lepoint and Mariana Raykova},
      title = {Secure Single-Server Aggregation with (Poly)Logarithmic Overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2020/704},
      year = {2020},
      doi = {10.1145/3372297.3417885},
      note = {\url{https://eprint.iacr.org/2020/704}},
      url = {https://eprint.iacr.org/2020/704}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.