Two-Tier Data Packing in RLWE-based Homomorphic Encryption for Secure Federated Learning

Homomorphic Encryption (HE) facilitates the preservation of privacy in federated learning (FL) aggregation. However, HE imposes significant computational and communication overhead. To address this problem, data encoding methods have been introduced that enable batch processing to improving the efficiency of ciphertext usage. The existing methods simply concatenate integer or coefficients assignment in polynomials, which do not fully make use of HE based on ring learning with errors (RLWE). We present a novel two-tier data encoding approach tailored for RLWE-based HE, effectively utilizing RLWE's polynomial structure. Our method involves a dual-level data packing strategy for batch processing at both integer and polynomial levels. At the first tier (integer level), we amalgamate those quantized model data into larger integers. Beyond existing concatenation-based encoding, we introduce a new encoding method derived from the Chinese Remainder Theorem (CRT). This CRT-based method effectively mitigates overflow and error propagation concerns. At the second tier (polynomial level), we transmute the large integers into a polynomial form. Additionally, we propose a new subring decomposition method, i.e., employing ring isomorphism mappings to project multiple large integers into varied sub-polynomial rings. Our dual-tier encoding strategy offers a more flexible and effective batch HE solution. We rigorously analyze the correctness, efficiency, and security of our approach. Our extensive experimental evaluations reveal that secure FL, empowered by our dual-tier encoding technique, markedly enhances computational and communication efficiencies over prevailing batch HE methods.