Privacy-Preserving Federated Averaging with Byzantine Aggregators in Asynchronous Networks

Federated Learning requires secure aggregation to prevent gradient leakage, yet existing protocols suffer from key limitations: they assume synchrony, require heavy peer-to-peer coordination, and do not tolerate aggregators that halt or omit messages. These constraints make current secure aggregation schemes impractical in large-scale, unreliable distributed settings.To overcome these limitations, we introduce a new secure aggregation protocol that operates in fully asynchronous networks, where messages may be arbitrarily delayed, and tolerates fully Byzantine aggregators that are capable of arbitrary deviations including premature halting. Our design combines several key mechanisms: clustering clients under verifiable coordinators, lightweight LWE-based masking (with masking components distributed across aggregators), and differential privacy applied to both intermediary and final aggregated models. We further propose verifiable shuffling of clients across clusters, which prevents any client from being systematically excluded by a Byzantine coordinator, and a fair inclusion mechanism that ensures the inclusion of straggling clients whose messages are late. The protocol eliminates all client-to-client communication, and its communication overhead scales only with the number of aggregators. It also ensures equal representation of clients across rounds, avoiding bias and preventing unbalanced privacy risks among clients. Overall, our protocol provides the first secure aggregation primitive that is both privacy-preserving and robust to fully Byzantine behavior in asynchronous networks, closing the gap between prior secure aggregation assumptions and real-world distributed systems.