Beyond Gradient Inversion: Hidden Subset Sum Problem-Based Input Reconstruction for Federated Learning

In this paper, we introduce Hidden Subset Sum Problem (HSSP), a problem rooted in computational complexity and cryptographic applications, as a rigorous mathematical framework for analyzing privacy vulnerabilities in federated learning (FL). By applying HSSP to FL, this work addresses the limitations of gradient inversion attacks (GIA) by overcoming key challenges such as dependence on label diversity and poor performance with large batch sizes, which hinder existing empirical GIA methods. Additionally, our analysis uncovers the fundamental reasons behind the degradation of empirical GIA with increasing batch sizes. We further demonstrate that employing secure data aggregation techniques, such as secure multiparty computation, can significantly increase the attack's time complexity. To the best of our knowledge, this is the first study to establish the connection between HSSP and FL, providing a robust analytical foundation for developing defense strategies and guiding future research.