ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitment

Tayyebeh Jahani-Nezhad, Mohammad Ali Maddah-Ali, Giuseppe CaireIEEE Trans. Information Theory 2025 · DOI

TL;DR

This paper introduces ByzSecAgg, a novel secure aggregation scheme for federated learning that is robust against Byzantine attacks and preserves data privacy. It achieves this by combining coded computing techniques with vector commitments, significantly reducing communication overhead compared to existing methods while maintaining strong security guarantees.

What Problem Does This Paper Address?

Federated Learning (FL) allows multiple devices to collaboratively train a global model without sharing their raw data. However, this decentralized approach faces two major challenges: privacy leakage and Byzantine attacks.

  • Privacy Leakage: Even without direct data sharing, a malicious server can potentially infer sensitive information about individual users' data from their model updates.
  • Byzantine Attacks: Some users might be malicious (Byzantine adversaries) and intentionally send corrupted or manipulated updates to poison the global model or disrupt the training process. Additionally, users might drop out unexpectedly, which the system needs to handle gracefully.

Existing secure aggregation schemes often struggle with high communication costs, especially for edge devices with limited bandwidth. Furthermore, many Byzantine-robust methods require the server to process individual model updates, which can compromise privacy. This paper aims to develop a scheme that is efficient, private, and robust against both Byzantine adversaries and dropouts, without requiring the server to see individual updates.

Methods

ByzSecAgg employs a multi-pronged approach, integrating several advanced techniques:

  • Coded Computing & Ramp Secret Sharing: Local model updates are first partitioned into smaller sub-vectors. These sub-vectors are then shared among users using a technique called "ramp secret sharing." This method allows for efficient sharing and verification. To enable privacy-preserving computation of pairwise distances (crucial for outlier detection), a second round of ramp sharing is performed, embedding the data differently in the sharing polynomial. This is inspired by coded computing principles.
  • Vector Commitment: To ensure the integrity of the shared data and prevent adversaries from tampering with their shares or commitments, a vector commitment scheme is used. This scheme allows users to commit to their data in a way that is binding (cannot be changed) and computationally hiding (reveals no information about the data itself), while still enabling verification. The key innovation here is a commitment scheme whose size remains constant, regardless of the size of the local update.
  • Distance-Based Outlier Detection (Multi-Krum): The pairwise distances between local updates are computed in a privacy-preserving manner using the secret shares. These distances are then used by the server with the multi-Krum algorithm to identify and filter out potentially malicious or outlier updates. This is a standard technique for Byzantine robustness, but ByzSecAgg enables it in a privacy-preserving way.
  • Reed-Solomon Decoding: This error-correction technique is used by the server to recover the aggregated model updates and pairwise distances from the received shares, even in the presence of some adversarial or dropped-out users.

Datasets

Not discussed in the paper. The paper focuses on the theoretical framework and algorithmic design for federated learning, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Privacy-Preserving Pairwise Distance Computation: The most significant insight is the development of a method to compute pairwise distances between local updates without revealing the updates themselves. This is achieved through a clever combination of ramp secret sharing and coded computing, allowing for distance calculations on encrypted shares.
  • Constant-Size Commitments for Scalability: Using a vector commitment scheme with a commitment size independent of the data length is crucial for efficiency, especially in FL settings with potentially large models. This contrasts with some prior methods where commitment size scales with data size.
  • Synergy of Coded Computing and Cryptography: The paper demonstrates a powerful synergy between coded computing (for efficient computation and communication) and cryptographic primitives (for security and privacy) to address complex challenges in distributed learning.
  • Robustness without Server Inspection of Individual Updates: ByzSecAgg achieves Byzantine robustness by enabling the server to recover aggregated information and pairwise distances from shares, rather than requiring it to inspect individual user updates. This is a key privacy advantage.

Key Results

  • Significant Communication Load Reduction: ByzSecAgg demonstrates a substantial reduction in both server and per-user communication loads compared to the baseline scheme BREA, especially as the number of users (N) and model size (L) increase.
  • Constant Commitment Size: The commitment size remains constant regardless of the local update size, which is a significant advantage for scalability.
  • Byzantine-Resistant and Privacy-Preserving: The scheme is proven to be robust against up to A Byzantine adversaries, D dropouts, and T colluding users, while ensuring that individual local updates remain private.
  • Theoretical Guarantees: The paper provides theoretical guarantees for the convergence of the global model and the resilience against various adversarial attacks.

Limitations and Future Work

  • Parameter Selection: The performance and security of ByzSecAgg depend on the careful selection of parameters like K (number of partitions) and m (number of selected users for aggregation). The paper suggests choosing these parameters to minimize communication loads and ensure robustness.
  • Computational Complexity: While communication is reduced, the computational complexity at the user and server can still be significant, particularly due to polynomial interpolation and secret sharing operations. The paper notes that the complexity for the server is O((N³ + V) log² N), where V is related to the number of users.
  • Field Size Requirements: The choice of a sufficiently large finite field is crucial for accuracy, and the paper provides conditions for this field size.
  • Future Work: The paper suggests that alternative robust aggregation methods could be employed within the ByzSecAgg framework, potentially requiring modifications to the scheme. The authors also highlight the importance of parameter selection for optimal performance.

Summary updated

BibTeX
@article{jahaninezhad2025byzsecagg,
  author = {Tayyebeh Jahani-Nezhad and Mohammad Ali Maddah-Ali and Giuseppe Caire},
  title = {{ByzSecAgg: A Byzantine-Resistant Secure Aggregation Scheme for Federated Learning Based on Coded Computing and Vector Commitment}},
  journal = {IEEE Trans. Information Theory},
  year = {2025},
  doi = {10.1109/tit.2025.3577019},
}
Figure