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

Abstract

We propose <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SwiftAgg+</monospace> , a novel secure aggregation protocol for federated learning systems, where a central server aggregates local models of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$N \in \mathbb {N}$ </tex-math></inline-formula> distributed users, each of size <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$L \in \mathbb {N}$ </tex-math></inline-formula> , trained on their local data, in a privacy-preserving manner. <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SwiftAgg+</monospace> 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 <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$D=o(N)$ </tex-math></inline-formula> dropout users, <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SwiftAgg+</monospace> achieves a per-user communication load of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\left({1+\mathcal {O}\left({\frac {1}{N}}\right)}\right)L$ </tex-math></inline-formula> symbols and a server communication load of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\left({1+\mathcal {O}\left({\frac {1}{N}}\right)}\right)L$ </tex-math></inline-formula> symbols, with a worst-case information-theoretic security guarantee, against any subset of up to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T=o(N)$ </tex-math></inline-formula> semi-honest users who may also collude with the curious server. Moreover, the proposed <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SwiftAgg+</monospace> allows for a flexible trade-off between communication loads and the number of active communication links. In particular, for <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$T&lt; N-D$ </tex-math></inline-formula> and for any <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$K\in \mathbb {N}$ </tex-math></inline-formula> , <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">SwiftAgg+</monospace> can achieve the server communication load of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\left({1+\frac {T}{K}}\right)L$ </tex-math></inline-formula> symbols, and per-user communication load of up to <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\left({1+\frac {T+D}{K}}\right)L$ </tex-math></inline-formula> symbols, where the number of pair-wise active connections in the network is <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\frac {N}{2}(K+T+D+1)$ </tex-math></inline-formula> .

Topics & Concepts