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(\sqrt{n})$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>O</mml:mi> <mml:mo>(</mml:mo> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> . 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>k</mml:mi> <mml:mo>=</mml:mo> <mml:mn>8</mml:mn> </mml:mrow> </mml:math> participants, our scheme achieves a ciphertext bootstrapping time of 0.048 seconds, representing a $$6.8 \times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>6.8</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> 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 \times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1.7</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> smaller) and 64KB for re-linearization keys ( $$6.0 \times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>6.0</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> smaller) relative to Kwak et al.’s implementation.