Multi-Group Fully Homomorphic Encryption Scheme Based on LWE and NTRU

Multi-Group Homomorphic Encryption (MGHE) is a pivotal advance in secure multi-party computation, integrating merits of Multi-Party Homomorphic Encryption (MPHE) and Multi-Key Homomorphic Encryption (MKHE) to eliminate MPHE’s fixed-party limitation and mitigate MKHE’s ciphertext expansion from dynamic enrollment. However, the efficient single-key FINAL scheme cannot extend to multi-party scenarios, due to the challenge of defining valid multiplication for vector NTRU ciphertexts, which hinders its use in multi-group bootstrapping and curbs efficiency.
To address this, additive secret sharing is adopted to convert vector NTRU ciphertext multiplication into secret share multiplication, enabling shared bootstrapping key generation within groups. For the first time, a multi-group ciphertext bootstrapping algorithm based on LWE and NTRU is proposed. Bootstrapping tasks are decomposed for parallel processing, and a hybrid product algorithm is designed to aggregate subtask outputs, boosting multi-group bootstrapping speed to match that of single-key ciphertexts. Noise accumulation is analyzed, with 100-bit and 128-bit security parameter sets selected for validation. Experiments show that 30/50-party multi-group bootstrapping takes only 1.87/2.58 seconds respectively.