Secure Single-Server Aggregation with (Poly)Logarithmic Overhead
| Autor: | Tancrède Lepoint, Keith Bonawitz, Mariana Raykova, James Bell, Adrià Gascón |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
0301 basic medicine
Correctness Cryptographic primitive Degree (graph theory) Shuffling business.industry Computer science 020206 networking & telecommunications 02 engineering and technology 03 medical and health sciences Task (computing) 030104 developmental biology 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) Differential privacy business Protocol (object-oriented programming) Computer network |
| Zdroj: | CCS |
| DOI: | 10.1145/3372297.3417885 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|