Secure Single-Server Aggregation with (Poly)Logarithmic Overhead

By James Bell, Kallista A. Bonawitz, Adrià Gascón, Tancrède Lepoint, Mariana Raykova. 2020

580 citations recorded by the source corpus.

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 settings where the adversary controls the server and a δ-fraction of the clients, and correctness with up to δ-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.

Subfields: Federated & Distributed Learning, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Federated & Distributed Learning

In Privacy & Security

Citations in the corpus

The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation (2021, methodology): “…Kairouz et al., 2019), cryptographic secure aggregation (SecAgg) to prevent a server from inspecting individual user updates (Bonawitz et al., 2017; Bell et al., 2020), and differentially private stochastic gradient descent (DP-SGD) to train models with provably limited information leakage (Abadi…”
Privacy Amplification by Decentralization (2020, background): “…to securely aggregate user contributions (Dwork et al., 2006a; Shi et al., 2011; Bonawitz et al., 2017; Chan et al., 2012b; Jayaraman et al., 2018; Bell et al., 2020; Sabater et al., 2020) or to securely shuﬄe the set of user messages so as to hide their source (Cheu et al., 2019; Erlingsson et…”
Flower: A Friendly Federated Learning Research Framework (2020, methodology): “To further protect clients’ local data, Flower provides implementation of both SecAgg (Bonawitz et al., 2017) and SecAgg + (Bell et al., 2020) protocols for a semi-honest threat model.”
Robust Aggregation for Federated Learning (2019, methodology): “In practice, a secure average oracle is implemented using cryptographic protocols based on secure multi-party computation [13, 17].”
Papaya: Practical, Private, and Scalable Federated Learning (2021, background): “Existing SMPC-based SecAgg approaches (Bonawitz et al., 2016; Bell et al., 2020; So et al., 2021b) hinder asynchronous training, as they require cohort formulation and inter-client communication in each round.”
Federated Learning with Buffered Asynchronous Aggregation (2021, background): “SecAgg is a privacy enhancing technology based on cryptographic primitives (Bonawitz et al., 2016; Bell et al., 2020; So et al., 2021) or hardware-based Trusted Execution Environment (TEE) (Karl et al.”
Privacy-Enhanced Federated Learning Against Poisoning Adversaries (2021, background): “SMC realizes private and correct computation through multiple interactions between participants [13], [14].”
A Survey on Federated Learning Systems: Vision, Hype and Reality for Data Privacy and Protection (2019, background): “aggregation [15] is applicable to protect the communicated message in case of party drop out.”