On the Information Theoretic Secure Aggregation With Uncoded Groupwise Keys

Kai Wan, Xin Yao, Hua Sun, Mingyue Ji, Giuseppe CaireIEEE Trans. Information Theory 2024 · DOI

TL;DR

This paper introduces a new secure aggregation scheme for federated learning that uses "uncoded groupwise keys" instead of the more complex "coded keys" typically used. They show that when the group size for keys is large enough relative to the number of users and dropouts, this simpler key sharing achieves the same optimal communication efficiency as existing methods.

What Problem Does This Paper Address?

Federated learning allows multiple users to collaboratively train a machine learning model without sharing their raw data. A crucial component is "secure aggregation," where a central server combines the model updates from users while ensuring no information about individual users' data is leaked. A key challenge is handling user dropouts – users who might stop participating during the process. Existing information-theoretic secure aggregation schemes often rely on complex "coded keys" that are shared among users. This paper addresses the limitations of these coded keys by exploring the use of simpler, "uncoded groupwise keys," where each key is shared by a specific group of users and is independent of other keys. The goal is to understand the communication cost implications of using these simpler keys, especially in the presence of user dropouts.

Methods

The authors formulate a new information-theoretic secure aggregation problem with the constraint of using uncoded groupwise keys. They then develop a novel secure aggregation scheme based on linear coding and interference alignment techniques. The core of their approach involves carefully designing coefficients for the transmitted messages that leverage the properties of these uncoded keys. They analyze two main scenarios:

  1. S > K - U: Where S is the group size for keys, K is the total number of users, and U is the minimum number of surviving users. In this case, they propose a scheme that achieves the same optimal communication rate as schemes using any type of keys (coded or uncoded).
  2. S ≤ K - U: Here, they derive a converse bound showing that uncoded groupwise keys are strictly sub-optimal compared to coded keys.

They also implement their proposed scheme on Amazon EC2 to compare its performance against existing methods.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and experimental validation using simulated data generated over a finite field (Fq).

Key Insights and Ideas

  • Simpler Keys Can Be Optimal: The most surprising finding is that "uncoded groupwise keys," which are simpler to generate and share, can achieve the same optimal communication efficiency as complex "coded keys" under certain conditions (specifically, when the group size S is sufficiently large relative to K and U). This suggests a practical advantage for federated learning systems.
  • The Role of Group Size (S): The paper highlights that the effectiveness of uncoded groupwise keys is highly dependent on the parameter S. Increasing S beyond a certain threshold (K - U + 1) does not further improve communication efficiency, indicating a sweet spot for key sharing.
  • Trade-off in Sub-optimal Regimes: When S is small (S ≤ K - U), the use of uncoded groupwise keys leads to a strictly sub-optimal communication rate, demonstrating a clear trade-off between key simplicity and performance in these scenarios.
  • Interference Alignment for Security: The proposed scheme cleverly uses interference alignment techniques to ensure that the keys are not leaked to the server, even when users transmit masked model updates.

Key Results

  • Optimal Performance for S > K - U: The proposed scheme with uncoded groupwise keys achieves the same optimal capacity region (communication rate) as the best schemes using any type of keys when S > K - U.
  • Sub-optimality for S ≤ K - U: For S ≤ K - U, uncoded groupwise keys lead to a strictly smaller capacity region compared to schemes that can use any keys.
  • Experimental Validation: The implemented scheme (GroupSecAgg) showed significant improvements in key sharing time (up to 31.7%) and model aggregation time (up to 53%) compared to existing schemes like LightSecAgg and SecAgg, respectively, on Amazon EC2.

Limitations and Future Work

  • Sub-optimal Case (S ≤ K - U): The paper identifies that for S ≤ K - U, uncoded groupwise keys are sub-optimal. Designing tight achievable schemes and converse bounds for this case remains an open problem.
  • Collusion: The current work assumes no collusion between the server and users. Extending the scheme to tolerate such collusion is a direction for future research.
  • Generalization: While the paper provides a framework for different regimes of U and K, further characterization of the capacity region for the case S ≤ K - U is ongoing.

Summary updated

Abstract

Secure aggregation, which is a core component of federated learning, aggregates locally trained models from distributed users at a central server. The “secure” nature of such aggregation consists of the fact that no information about the local users’ data must be leaked to the server except the aggregated local models. In order to guarantee security, some keys may be shared among the users (this is referred to as the key sharing phase). After the key sharing phase, each user masks its trained model which is then sent to the server (this is referred to as the model aggregation phase). This paper follows the information theoretic secure aggregation problem originally formulated by Zhao and Sun, with the objective to characterize the minimum communication cost from the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf K$ </tex-math></inline-formula> users in the model aggregation phase. Due to user dropouts, which are common in real systems, the server may not receive all messages from the users. A secure aggregation scheme should tolerate the dropouts of at most <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathsf K}-{\mathsf U}$ </tex-math></inline-formula> users, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf U$ </tex-math></inline-formula> is a system parameter. The optimal communication cost is characterized by Zhao and Sun, but with the assumption that the keys stored by the users could be any random variables with arbitrary dependency. On the motivation that uncoded groupwise keys are more convenient to be shared and could be used in large range of applications besides federated learning, in this paper we add one constraint into the above problem, namely, that the key variables are mutually independent and each key is shared by a group of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf S$ </tex-math></inline-formula> users, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\mathsf S$ </tex-math></inline-formula> is another system parameter. To the best of our knowledge, all existing secure aggregation schemes (with information theoretic security or computational security) assign coded keys to the users. We show that if <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathsf S}\gt {\mathsf K}-{\mathsf U}$ </tex-math></inline-formula>, a new secure aggregation scheme with uncoded groupwise keys can achieve the same optimal communication cost as the best scheme with coded keys; if <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathsf S}\leq {\mathsf K}-{\mathsf U}$ </tex-math></inline-formula>, uncoded groupwise key sharing is strictly sub-optimal. Finally, we also implement our proposed secure aggregation scheme into Amazon EC2, which are then compared with the existing secure aggregation schemes with offline key sharing.
BibTeX
@article{wan2024information,
  author = {Kai Wan and Xin Yao and Hua Sun and Mingyue Ji and Giuseppe Caire},
  title = {{On the Information Theoretic Secure Aggregation With Uncoded Groupwise Keys}},
  journal = {IEEE Transactions on Information Theory},
  year = {2024},
  doi = {10.1109/tit.2024.3422087},
}
Figure