Accelerating MKFHE bootstrapping via parallel-friendly NTRU-based blind rotation

Fully Homomorphic Encryption (FHE) enables arbitrary computations on encrypted data, a paradigm that Multi-Key FHE (MKFHE) extends to the decentralized setting by supporting operations on ciphertexts encrypted under multiple, distinct keys. However, the high computational cost of bootstrapping remains a major bottleneck, especially in the multi-key scenario where blind rotation is the dominant overhead. To address this, we propose a novel and parallel-friendly blind rotation scheme based on the NTRU assumption for efficient MKFHE bootstrapping. Our core technical contribution is a grouped inner product algorithm optimized for automorphism-based blind rotation, which reorganizes hybrid product storage and extends the external product to be compatible with both NTRU and MK-RLWE ciphertexts. Our parallelized algorithm reduces the time complexity from O ( n ) to O(√n) O ( n ) . Our scheme demonstrates significant improvements over prior MKFHE works in both computational efficiency and storage requirements. At a 100-bit security level with $$k=8$$ k = 8 participants, our scheme achieves a ciphertext bootstrapping time of 0.048 seconds, representing a 6.8 × 6.8 × speedup compared to Kwak et al.’s state-of-the-art work. Furthermore, our scheme substantially reduces storage overhead, requiring only 81.5MB for evaluation keys ( 1.7 × 1.7 × smaller) and 64KB for re-linearization keys ( 6.0 × 6.0 × smaller) relative to Kwak et al.’s implementation.