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 was adopted to convert vector NTRU ciphertext multiplication into secret share multiplication, enabling shared bootstrapping key generation within groups. A new multi-group ciphertext bootstrapping algorithm for MGHE was developed via the integration of LWE and NTRU cryptographic primitives. Bootstrapping tasks were decomposed for parallel processing, and a hybrid product algorithm was designed to aggregate subtask outputs, boosting multi-group bootstrapping speed to match that of single-key ciphertexts. Noise accumulation was analyzed, with 100-bit and 128-bit security parameter sets selected for validation. Experiments showed that 30- and 50-party multi-group bootstrapping takes only 1.87 s and 2.58 s respectively.