<p>Polynomial multiplication serves as a fundamental computational primitive in modern cryptography–including fully homomorphic encryption and zero-knowledge proofs –as well as in digital signal processing. Its performance optimization has become increasingly critical amid the rapid development of privacy-preserving computation and blockchain technologies. To address the limitations of traditional algorithms in meeting the demands for high throughput and low latency, this study proposes a high-performance polynomial multiplication accelerator based on the collaborative optimization of GPU-NTT and the Karatsuba algorithm. The method deeply integrates the asymptotically optimal complexity of NTT with the constant-factor efficiency of Karatsuba at moderate scales, and fully exploits the parallel computing power of GPUs to construct a modular, multi-stage pipelined acceleration framework. The divide-and-conquer nature of the Karatsuba algorithm is leveraged for coarse-grained parallelism, splitting large polynomial multiplications into subproblems handled by GPU thread blocks in parallel, while each subproblem is solved with fine-grained parallelism using GPU-accelerated NTT kernels. An innovative zero-padding strategy is introduced to enhance the generality of the NTT kernels, and shared memory caching is employed to alleviate GPU memory bandwidth bottlenecks. Experimental results on the NVIDIA RTX 4060 GPU demonstrate that the proposed method achieves a stable speedup of 1.43<InlineEquation ID="IEq1"><EquationSource Format="TEX">$\times $</EquationSource><EquationSource Format="MATHML"><math><mo>×</mo></math></EquationSource></InlineEquation> to 1.49<InlineEquation ID="IEq2"><EquationSource Format="TEX">$\times $</EquationSource><EquationSource Format="MATHML"><math><mo>×</mo></math></EquationSource></InlineEquation> over the baseline GPU-NTT for lower-dimensional polynomials, and outperforms the KNTT algorithm by up to 2.44<InlineEquation ID="IEq3"><EquationSource Format="TEX">$\times $</EquationSource><EquationSource Format="MATHML"><math><mo>×</mo></math></EquationSource></InlineEquation> for higher dimensions (e.g., <InlineEquation ID="IEq4"><EquationSource Format="TEX">$\log _2 n = 14$</EquationSource><EquationSource Format="MATHML"><math><mrow><msub><mo>log</mo><mn>2</mn></msub><mi>n</mi><mo>=</mo><mn>14</mn></mrow></math></EquationSource></InlineEquation>), showing superior scalability and robustness. Kernel execution time analysis further confirms that the method benefits from efficient kernel fusion and balanced workload distribution, which effectively avoids pipeline stalls and ensures high-throughput execution. This research provides a significant performance optimization solution for the practical deployment of advanced cryptographic technologies such as FHE and ZKP.</p>

GPU-oriented implementation and optimization of Karatsuba–NTT polynomial multiplication

期刊论文
出版模式：

开放获取
发表日期：

2026年5月7日

查看全文

Ruwei Huang,
Xiaolong Tang,
Junjie Wang,
Xuezheng Qin

摘要

Polynomial multiplication serves as a fundamental computational primitive in modern cryptography–including fully homomorphic encryption and zero-knowledge proofs –as well as in digital signal processing. Its performance optimization has become increasingly critical amid the rapid development of privacy-preserving computation and blockchain technologies. To address the limitations of traditional algorithms in meeting the demands for high throughput and low latency, this study proposes a high-performance polynomial multiplication accelerator based on the collaborative optimization of GPU-NTT and the Karatsuba algorithm. The method deeply integrates the asymptotically optimal complexity of NTT with the constant-factor efficiency of Karatsuba at moderate scales, and fully exploits the parallel computing power of GPUs to construct a modular, multi-stage pipelined acceleration framework. The divide-and-conquer nature of the Karatsuba algorithm is leveraged for coarse-grained parallelism, splitting large polynomial multiplications into subproblems handled by GPU thread blocks in parallel, while each subproblem is solved with fine-grained parallelism using GPU-accelerated NTT kernels. An innovative zero-padding strategy is introduced to enhance the generality of the NTT kernels, and shared memory caching is employed to alleviate GPU memory bandwidth bottlenecks. Experimental results on the NVIDIA RTX 4060 GPU demonstrate that the proposed method achieves a stable speedup of 1.43$\times $ $\times$ to 1.49$\times $ $\times$ over the baseline GPU-NTT for lower-dimensional polynomials, and outperforms the KNTT algorithm by up to 2.44$\times $ $\times$ for higher dimensions (e.g., $\log _2 n = 14$ ${log}_{2} n = 14$ ), showing superior scalability and robustness. Kernel execution time analysis further confirms that the method benefits from efficient kernel fusion and balanced workload distribution, which effectively avoids pipeline stalls and ensures high-throughput execution. This research provides a significant performance optimization solution for the practical deployment of advanced cryptographic technologies such as FHE and ZKP.