Accelerating Number Theoretic Transformations for Bootstrappable Homomorphic Encryption on GPUs

Sangpyo Kim, Wonkyung Jung, Jaiyoung Park, Jung Ho Ahn

TL;DR

This paper tackles the challenge of accelerating Number Theoretic Transforms (NTTs), a crucial component for efficient Homomorphic Encryption (HE), on GPUs. By analyzing the differences between NTT and its cousin, the Discrete Fourier Transform (DFT), the authors identify a main-memory bandwidth bottleneck in NTT and propose a novel "on-the-fly twiddling" (OT) technique to overcome it, achieving significant speedups.

What Problem Does This Paper Address?

Homomorphic Encryption (HE) allows computations on encrypted data, promising enhanced privacy. A key bottleneck in HE is the performance of Number Theoretic Transforms (NTTs), which are essential for fast polynomial multiplication on encrypted data. While previous work has adapted optimizations from the related Discrete Fourier Transform (DFT) to accelerate NTTs on GPUs, these efforts often overlook fundamental algorithmic differences between NTT and DFT. This leads to suboptimal implementations that don't fully address the unique challenges of NTT, particularly the severe main-memory bandwidth limitations that arise when dealing with the large parameters required for practical HE applications like bootstrapping. The paper aims to bridge this gap by providing a comprehensive analysis of NTT's characteristics on GPUs and proposing a tailored solution.

Methods

The authors begin by dissecting the algorithmic differences between NTT and DFT, focusing on their computational requirements and performance characteristics on modern GPUs. They then systematically evaluate common FFT optimization techniques, such as batching, register-based high-radix implementations, and shared memory (SMEM) usage, to understand their impact on NTT performance.

The core novelty of this work lies in the proposed on-the-fly twiddling (OT) scheme. Unlike traditional approaches that precompute all "twiddle factors" (complex numbers used in DFT, or their modular arithmetic equivalents in NTT), OT generates some of these factors dynamically. This is achieved by leveraging the associative property of multiplication and avoiding expensive modulo operations during generation. OT aims to reduce the size of precomputed tables, thereby decreasing main-memory accesses and alleviating the bandwidth bottleneck.

The paper also explores various implementation strategies, including:

  • Cooley-Tukey vs. Stockham algorithms: While Stockham is often preferred for DFT due to its in-place nature, the authors opt for Cooley-Tukey for NTT, justifying it by the lack of strict in-place requirements for HE NTT and potential for better memory coalescing.
  • Shared Memory (SMEM) Implementation: This technique uses SMEM as intermediate storage to reduce main memory accesses, crucial for large NTT computations.
  • Register-based High-Radix Implementation: This aims to perform more computations per thread by utilizing GPU registers, but is limited by register availability and potential "register spills" to slower memory.

Datasets

Not discussed in the paper. The evaluation focuses on synthetic workloads representative of HE parameters.

Key Insights and Ideas

  • NTT's Main-Memory Bottleneck: The most significant finding is that even after applying standard DFT optimizations, NTT implementations on GPUs are severely limited by main-memory bandwidth, especially for the large parameter sets needed for bootstrappable HE. This is due to the larger precomputed tables required for NTT compared to DFT.
  • OT's Effectiveness: The proposed "on-the-fly twiddling" (OT) technique directly addresses the memory bandwidth issue by reducing the need for large precomputed tables. This is a crucial insight, as generating twiddle factors on-the-fly for NTT was previously considered inefficient due to the cost of modular arithmetic.
  • Trade-offs in GPU Optimization: The paper highlights the intricate trade-offs involved in GPU optimization for NTT. For instance, increasing the radix (number of operations per thread) can improve performance by reducing memory accesses but can also lead to register spills and reduced occupancy if not managed carefully. Similarly, using shared memory can reduce global memory accesses but introduces synchronization overhead.
  • NTT vs. DFT Nuances: The study emphasizes that simply porting DFT optimizations to NTT is insufficient. The inherent differences in their mathematical operations and data structures necessitate tailored approaches. For example, NTT's need for modular arithmetic and the nature of its twiddle factors create distinct performance characteristics.

Key Results

  • The proposed on-the-fly twiddling (OT) scheme, when combined with other optimizations like SMEM implementation, achieved a significant 4.2x speedup on average compared to a baseline radix-2 NTT implementation for large HE parameters.
  • The OT technique alone provided an average speedup of 9.3% by reducing DRAM accesses and improving bandwidth utilization.
  • The study found that a radix of 16 was optimal for register-based high-radix NTT implementations, offering a 2.41x speedup, while higher radices led to performance degradation due to register spills.
  • SMEM implementations consistently outperformed register-based high-radix implementations for NTT.
  • The paper demonstrated that batching NTT operations significantly improves GPU utilization and performance, with saturation occurring around a batch size of 5.

Limitations and Future Work

  • Parameter Sensitivity: While the paper explores various HE parameters, the optimal configuration of optimizations might still be sensitive to specific HE schemes and their parameter choices.
  • Hardware Specificity: The optimizations and performance figures are based on a specific GPU architecture (NVIDIA Titan V). Further exploration on different GPU architectures might yield varied results.
  • Future Work: The authors suggest further research into exploring more advanced FFT-based optimization techniques and their applicability to NTT. Investigating hardware-specific features and their interplay with NTT algorithms could also lead to further performance gains. The paper also implicitly points towards the need for more sophisticated memory management strategies for NTT on GPUs.

Summary updated

Abstract

Homomorphic encryption (HE) draws huge attention as it provides a way of privacy-preserving computations on encrypted messages. Number Theoretic Transform (NTT), a specialized form of Discrete Fourier Transform (DFT) in the finite field of integers, is the key algorithm that enables fast computation on encrypted ciphertexts in HE. Prior works have accelerated NTT and its inverse transformation on a popular parallel processing platform, GPU, by leveraging DFT optimization techniques. However, these GPU-based studies lack a comprehensive analysis of the primary differences between NTT and DFT or only consider small HE parameters that have tight constraints in the number of arithmetic operations that can be performed without decryption. In this paper, we analyze the algorithmic characteristics of NTT and DFT and assess the performance of NTT when we apply the optimizations that are commonly applicable to both DFT and NTT on modern GPUs. From the analysis, we identify that NTT suffers from severe main-memory bandwidth bottleneck on large HE parameter sets. To tackle the main-memory bandwidth issue, we propose a novel NTT-specific on-the-fly root generation scheme dubbed on-the-fly twiddling (OT). Compared to the baseline radix-2 NTT implementation, after applying all the optimizations, including OT, we achieve 4.2× speedup on a modern GPU.
BibTeX
@inproceedings{kim2020accelerating,
  author = {Sangpyo Kim and Wonkyung Jung and Jaiyoung Park and Jung Ho Ahn},
  title = {{Accelerating Number Theoretic Transformations for Bootstrappable Homomorphic Encryption on GPUs}},
  booktitle = {IISWC},
  year = {2020},
  url = {https://openreview.net/forum?id=no1QmHQqSa},
}
Figure