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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$O(\sqrt{n})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo stretchy="false">(</mo> <msqrt> <mi>n</mi> </msqrt> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. Our scheme demonstrates significant improvements over prior MKFHE works in both computational efficiency and storage requirements. At a 100-bit security level with <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$k=8$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>k</mi> <mo>=</mo> <mn>8</mn> </mrow> </math></EquationSource> </InlineEquation> participants, our scheme achieves a ciphertext bootstrapping time of 0.048 seconds, representing a <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$6.8 \times$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>6.8</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation> 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 (<InlineEquation ID="IEq4"> <EquationSource Format="TEX">$1.7 \times$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>1.7</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation> smaller) and 64KB for re-linearization keys (<InlineEquation ID="IEq5"> <EquationSource Format="TEX">$6.0 \times$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>6.0</mn> <mo>×</mo> </mrow> </math></EquationSource> </InlineEquation> smaller) relative to Kwak et al.’s implementation.

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

期刊论文
出版模式：

开放获取
发表日期：

2026年3月13日

查看全文

Yiran Dai,
Binwu Xiang,
Yi Deng,
Jiang Zhang

摘要

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})$ $O (\sqrt{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 \times$ $6.8 \times$ 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$ $1.7 \times$ smaller) and 64KB for re-linearization keys ( $6.0 \times$ $6.0 \times$ smaller) relative to Kwak et al.’s implementation.