VSAFL: Verifiable and Secure Aggregation With (Poly) Logarithmic Overhead in Federated Learning

Federated learning (FL) is a distributed machine learning framework that enables multiple participants to train models without directly sharing local data. However, sensitive information about participants may still be leaked through their gradients. Furthermore, centralized servers used for aggregating these gradients can be vulnerable to compromise, leading to privacy violations or other malicious attacks. Therefore, it is essential to verify the integrity of the aggregation. In this work, we focus on designing communication efficient and fast verifiable aggregations for FL. We propose VSAFL, a verifiable secure aggregation (SecAgg) protocol specifically designed for cross-device FL. VSAFL achieves computation and communication cost of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\log ^{2} n + l \log n)$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$O(\log n + l)$ </tex-math></inline-formula>, respectively, for SecAgg and verification for each user in each epoch, where n represents the number of clients and l denotes the dimension of the gradient vector. By employing a lightweight cryptographic primitive pseudorandom generator, VSAFL enables central servers and clients to prove and verify the correctness of model aggregations, significantly reducing verification costs. Our polynomial logarithmic overhead is particularly advantageous for clients with limited resources and high-dimensional gradients. Additionally, the proposed protocol is to be fully robust to clients dropping at any point. Through experimental evaluation, we demonstrate that VSAFL outperforms prior work in terms of verification speed by orders of magnitude.