SwiftAgg+: Achieving Asymptotically Optimal Communication Loads in Secure Aggregation for Federated Learning

Tayyebeh Jahani-Nezhad, Mohammad Ali Maddah-Ali, Songze Li, Giuseppe Caire

TL;DR

This paper introduces SwiftAgg+, a novel secure aggregation protocol for federated learning that significantly reduces communication overhead while maintaining strong privacy guarantees. It achieves near-optimal communication loads, even in the presence of user dropouts and semi-honest adversaries, by introducing a flexible trade-off between communication efficiency and network connectivity.

What Problem Does This Paper Address?

Federated Learning (FL) allows multiple devices to collaboratively train a machine learning model without sharing their raw data. A crucial step in FL is "secure aggregation," where a central server combines the local model updates from many devices. However, existing secure aggregation protocols often suffer from high communication costs, requiring devices to send large amounts of data to the server. This is particularly problematic for devices with limited bandwidth or intermittent connectivity. Furthermore, these protocols need to be robust against users who might drop out during the process and protect against adversaries (including the server itself) who might try to infer private information from the transmitted data. The challenge is to design a protocol that is communication-efficient, resilient to dropouts, and provides strong, information-theoretic privacy guarantees.

Methods

SwiftAgg+ tackles the problem by introducing a hierarchical, tree-based aggregation structure and a novel partitioning and secret sharing scheme.

  • Hierarchical Aggregation Tree: Users are organized into groups, and these groups are arranged in a tree structure with the server at the root. This allows for a staged aggregation process, starting within groups and then progressing up the tree.
  • Model Partitioning: Each user's local model is divided into $K$ smaller parts.
  • Ramp Secret Sharing: Within each group, these model partitions are shared using a ramp secret sharing scheme. This scheme offers a trade-off between the number of shares and the information leaked, providing privacy against a limited number of colluding users.
  • Intra- and Inter-Group Aggregation: Users within a group first aggregate their shared model parts. Then, these aggregated shares are passed up the aggregation tree to parent groups, and eventually to the server.
  • Flexible Trade-off: A key innovation is the introduction of a parameter $K$. By adjusting $K$, SwiftAgg+ allows for a flexible trade-off between communication load and the number of active network connections. A larger $K$ reduces communication load but increases the number of connections, while a smaller $K$ does the opposite.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and protocol design, not empirical evaluation on specific datasets.

Key Insights and Ideas

  • Hierarchical Aggregation as a Communication Bottleneck Reducer: Structuring the aggregation process in a tree allows for localized computations and reduces the overall communication burden on individual users and the server compared to flat, all-to-all communication.
  • Ramp Secret Sharing for Privacy: Using ramp secret sharing, instead of more complex schemes, provides a practical way to achieve information-theoretic privacy against a specified number of semi-honest users, balancing security with efficiency.
  • The Power of Parameter $K$: The introduction of parameter $K$ is a significant contribution, enabling a tunable balance between communication efficiency and network complexity. This is crucial for real-world FL deployments where network conditions vary greatly.
  • Near-Optimal Communication: The protocol achieves communication loads that are asymptotically close to the theoretical cut-set lower bounds, meaning it's very close to the best possible performance in terms of data transmission.
  • Dropout Resilience: The scheme is designed to handle user dropouts gracefully within a single communication round, avoiding the need for additional rounds to recover lost information, which is a common issue in other protocols.

Key Results

  • Server Communication Load: For $T = o(N)$ and $N-D = O(N)$, SwiftAgg+ achieves a server communication load of $(1 + O(1/N))L$ symbols, which is within a factor of 1 of the cut-set lower bound.
  • Per-User Communication Load: For $T = o(N)$ and $D = o(N)$, the per-user communication load is $(1 + O(1/N))L$ symbols.
  • Dropout Tolerance: The protocol is resilient to up to $D$ user dropouts.
  • Security Guarantee: It provides worst-case information-theoretic security against up to $T < N-D$ semi-honest users who may collude with each other and the server.
  • Flexible Trade-off: By adjusting parameter $K$, the server communication load can be expressed as $1 + T/(N-T-D-K)$ and per-user load as $1 + (T+D)/K$, demonstrating the tunable nature of the scheme.

Limitations and Future Work

  • Assumptions: The protocol assumes error-free communication links and a known number of semi-honest users ($T$) and dropouts ($D$).
  • Complexity of Tree Structure: While the tree structure offers flexibility, the optimal choice of the aggregation tree topology might depend on the specific network connectivity and could be a subject for future research.
  • Practical Implementation: The paper focuses on theoretical guarantees. Future work could involve empirical evaluation on real-world FL systems to assess performance under realistic network conditions and with various model architectures.
  • Semi-Honest vs. Malicious Adversaries: The current security guarantees are against semi-honest adversaries. Extending this to malicious adversaries (who can deviate arbitrarily from the protocol) would be a significant challenge.

Summary updated

Abstract

We propose SwiftAgg+, a novel secure aggregation protocol for federated learning systems, where a central server aggregates local models of $N \in \mathbb{N}$ distributed users, each of size $L \in \mathbb{N}$, trained on their local data, in a privacy-preserving manner. SwiftAgg+ can significantly reduce the communication overheads without any compromise on security, and achieve optimal communication loads within diminishing gaps. Specifically, in presence of at most $D=o(N)$ dropout users, SwiftAgg+ achieves a per-user communication load of $(1+\mathcal{O}(\frac{1}{N}))L$ symbols and a server communication load of $(1+\mathcal{O}(\frac{1}{N}))L$ symbols, with a worst-case information-theoretic security guarantee, against any subset of up to $T=o(N)$ semi-honest users who may also collude with the curious server. Moreover, the proposed SwiftAgg+ allows for a flexible trade-off between communication loads and the number of active communication links. In particular, for $T<N-D$ and for any $K\in\mathbb{N}$, SwiftAgg+ can achieve the server communication load of $(1+\frac{T}{K})L$ symbols, and per-user communication load of up to $(1+\frac{T+D}{K})L$ symbols, where the number of pair-wise active connections in the network is $\frac{N}{2}(K+T+D+1)$.
BibTeX
@article{jahaninezhad2023swiftagg,
  author = {Tayyebeh Jahani-Nezhad and Mohammad Ali Maddah-Ali and Songze Li and Giuseppe Caire},
  title = {{SwiftAgg+: Achieving Asymptotically Optimal Communication Loads in Secure Aggregation for Federated Learning}},
  journal = {IEEE J. Sel. Areas Commun.},
  year = {2023},
  url = {https://openreview.net/forum?id=2v1tLXmuWAG},
}
Figure