FedSSA: Reducing Overhead of Additive Cryptographic Methods in Federated Learning With Sketch

Federated Learning (FL) has been applied across diverse domains as a powerful technique but faces critical challenges in privacy protection. Secure aggregation and additive homomorphic encryption are two of the most commonly used cryptographic methods to protect model updates. To provide a strong privacy guarantee, both methods satisfy the additivity and require the integer form to encrypt model updates. However, they still suffer from a non-negligible overhead of the computation and communication. To mitigate such overhead, existing approaches of lossy compression (e.g., gradient compression) have been explored but exhibit the inapplicability of FL with additive cryptographic methods. In this paper, we propose FedSSA, a novel compression framework to reduce the overhead of additive cryptographic methods in FL based on two new techniques: (i) QSRHT Sketch, a sketch-based compression method that supports large compression ratios with a bounded error with the integer requirement, and (ii) periodic rehashing, which ensures the unbiasedness of QSRHT Sketch. Our evaluation shows that FEDSSA achieves a high compression ratio (<tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\times 160$</tex>) with a low model accuracy degradation (less than 5%). For additive homomorphic encryption, FEDSSA reduces the average computation time per round by up to 58.15 % compared to state-of-the-art compressor that support additive homomorphic encryption, with a low test accuracy drop (within 2.2 %).