Scholarlink

<p>Large polynomial multiplication is one of the computational bottlenecks in fully homomorphic encryption implementations. Usually, these multiplications are implemented using the number-theoretic transform to speed up the computation. State-of-the-art GPU-based implementation of fully homomorphic encryption computes the number theoretic transform in two different kernels, due to the necessary synchronization between GPU blocks to ensure correctness in computation. This can be a serious limitation in embedded systems that only have constrained computational resources to support the time-consuming homomorphic encryption. In this paper, we proposed a series of techniques to improve the performance of number theoretic transform targeting homomorphic encryption on a GPU device. Firstly, we proposed to arrange the polynomials in a transposed manner and skip the last two levels of radix-4 number theoretic transform, allowing us to completely avoid the block synchronization in NTT implementation. This technique improved the performance of homomorphic encryption by <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(1.37 \times\)</EquationSource> </InlineEquation> and <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(1.34 \times\)</EquationSource> </InlineEquation> on RTX 4060 and Jetson Orin Nano respectively, compared to the conventional approach that uses full NTT without skipping any levels. However, such an approach also introduces extra overhead in the subsequent point-wise multiplication, which slows down the homomorphic multiplication. To reduce this negative impact, a fast <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(16\times 16\)</EquationSource> </InlineEquation> point-wise multiplication implementation was proposed, which relies on the heavily optimized Toom-Cook 4-way algorithm. Experimental results show that our proposed homomorphic multiplication can achieve similar latency compared to Jung et al. and Yang et al., which are the best results to date. This shows that the proposed cuTraNTT is able to reduce the latency of homomorphic encryption without sacrificing the performance in homomorphic multiplication.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

cuTraNTT: GPU-based transposed number theoretic transform with low latency homomorphic encryption for IoT applications

  • 期刊论文

  • 发表日期：

    2026年7月14日

查看全文
  • Supriya Adhikary,
  • Wai-Kong Lee,
  • Angshuman Karmakar,
  • Yongwoo Lee,
  • Seong Oun Hwang,
  • Ramachandra Achar

摘要

Large polynomial multiplication is one of the computational bottlenecks in fully homomorphic encryption implementations. Usually, these multiplications are implemented using the number-theoretic transform to speed up the computation. State-of-the-art GPU-based implementation of fully homomorphic encryption computes the number theoretic transform in two different kernels, due to the necessary synchronization between GPU blocks to ensure correctness in computation. This can be a serious limitation in embedded systems that only have constrained computational resources to support the time-consuming homomorphic encryption. In this paper, we proposed a series of techniques to improve the performance of number theoretic transform targeting homomorphic encryption on a GPU device. Firstly, we proposed to arrange the polynomials in a transposed manner and skip the last two levels of radix-4 number theoretic transform, allowing us to completely avoid the block synchronization in NTT implementation. This technique improved the performance of homomorphic encryption by \(1.37 \times\) and \(1.34 \times\) on RTX 4060 and Jetson Orin Nano respectively, compared to the conventional approach that uses full NTT without skipping any levels. However, such an approach also introduces extra overhead in the subsequent point-wise multiplication, which slows down the homomorphic multiplication. To reduce this negative impact, a fast \(16\times 16\) point-wise multiplication implementation was proposed, which relies on the heavily optimized Toom-Cook 4-way algorithm. Experimental results show that our proposed homomorphic multiplication can achieve similar latency compared to Jung et al. and Yang et al., which are the best results to date. This shows that the proposed cuTraNTT is able to reduce the latency of homomorphic encryption without sacrificing the performance in homomorphic multiplication.