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

Abstract 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.