Accelerating NTRU based Homomorphic Encryption using GPUs

Wei Dai, Yarkin Doröz, Berk Sunar

TL;DR

This paper presents a novel GPU-accelerated library for homomorphic encryption, specifically targeting NTRU-based schemes. By leveraging the Chinese Remainder Theorem and optimized polynomial arithmetic on Nvidia GPUs, they achieve significant speedups for evaluating complex cryptographic operations, paving the way for more practical private computations.

What Problem Does This Paper Address?

Homomorphic Encryption (HE) is a revolutionary cryptographic technique that allows computations to be performed on encrypted data without decrypting it first. This has profound implications for privacy-preserving cloud computing, secure data analysis, and more. However, HE schemes have historically been plagued by two major bottlenecks: extreme computational slowness and massive memory requirements. While Gentry's groundbreaking work laid the foundation, practical implementations have been prohibitively slow, with evaluations of even moderately complex circuits taking hours or days. This paper aims to tackle the computational bottleneck by exploring the use of Graphics Processing Units (GPUs) to accelerate these demanding operations.

Methods

The core of this work lies in developing a specialized library for Nvidia GPUs to accelerate NTRU-based homomorphic encryption. The authors employ several key techniques:

  • Chinese Remainder Theorem (CRT) for Polynomial Decomposition: Large polynomials with big coefficients, which are central to HE operations, are decomposed into multiple smaller polynomials with smaller coefficients using CRT. This allows for computations to be performed in smaller residue rings, which are more amenable to parallel processing.
  • Discrete Fourier Transform (DFT) / Number Theoretic Transform (NTT): For efficient polynomial multiplication in these smaller rings, the authors utilize a custom-built discrete Fourier transform library. This is a standard technique for speeding up polynomial multiplication, but its implementation here is optimized for GPU architectures.
  • GPU Optimization: The entire library is built from the ground up for Nvidia GPUs. This involves careful memory management (using registers, shared memory, and global memory), optimized CUDA kernels for parallel execution, and leveraging GPU-specific instructions.
  • Homomorphic Evaluation Primitives: Beyond basic polynomial arithmetic, the library includes optimized implementations for the core homomorphic evaluation operations: addition, multiplication, and relinearization. Relinearization, in particular, is crucial for managing the "noise" that accumulates during HE computations.
  • Customized NTRU Scheme: The authors adapt a specific NTRU-based somewhat homomorphic encryption scheme (proposed by Doröz et al.) to leverage their GPU library. This involves using specific cyclotomic polynomials and a carefully chosen prime sequence for efficiency.

Datasets

Not discussed in the paper. The evaluation is performed on standard block ciphers (Prince and AES) using parameters derived from existing HE schemes.

Key Insights and Ideas

  • GPU Acceleration is Crucial for HE Efficiency: The paper strongly demonstrates that GPUs can provide substantial speedups for HE operations, making them a viable platform for accelerating these computationally intensive tasks.
  • CRT Decomposition is Key to Parallelism: Decomposing large polynomials via CRT is fundamental to unlocking the parallel processing capabilities of GPUs. It breaks down complex operations into smaller, independent tasks.
  • Memory is the Next Frontier: The authors identify GPU memory as a significant limiting factor. Even with computational speedups, the sheer size of ciphertexts and evaluation keys can bottleneck performance. This suggests that future improvements will depend on GPUs with larger memory capacities.
  • Tailoring HE Schemes for Hardware: The success of their GPU library highlights the importance of designing HE schemes with hardware acceleration in mind, considering factors like polynomial structure and prime choices.

Key Results

The paper reports significant speedups when evaluating block ciphers using their GPU-accelerated NTRU library compared to a software implementation on an Intel Xeon processor:

  • Prince Block Cipher: Achieved a speedup of 2.57x.
  • AES Block Cipher: Achieved a speedup of 7.6x.
  • General Operations: In Table II, they show speedups of ~2.8x for multiplication and ~12x for relinearization on average across Prince and AES, compared to CPU.
  • AES Evaluation Time: The homomorphic evaluation of AES is reduced to 4.15 hours, a significant improvement over previous results.

Limitations and Future Work

  • GPU Memory Bottleneck: The authors explicitly state that GPU memory is a limiting factor. They suggest that moving to GPUs with more memory would yield even greater speedups.
  • Parameter Selection: While they use specific parameter choices for NTRU, further exploration of parameter optimization for GPU architectures could be beneficial.
  • Generalizability: The library is currently focused on NTRU-based schemes. Extending it to other HE schemes (e.g., lattice-based) could broaden its impact.
  • Software Overhead: The reported timings do not include data type conversions from NTL to GPU-compatible formats, which could add some overhead.

The future work suggested by the authors revolves around addressing the memory limitations and potentially exploring other hardware platforms like FPGAs for further optimization.

Summary updated

Abstract

In this work we introduce a large polynomial arithmetic library optimized for Nvidia GPUs to support fully homomorphic encryption schemes. To realize the large polynomial arithmetic library we convert the polynomial with large coefficients using the Chinese Remainder Theorem into many polynomials with small coefficients, and then carry out modular multiplications in the residue space using a custom developed discrete Fourier transform library. We further extend the library to support the homomorphic evaluation operations, i.e. addition, multiplication, and relinearization, in an NTRU based somewhat homomorphic encryption library. Finally, we put the library to use to evaluate homomorphic evaluation of two block ciphers: Prince and AES, which show 2.57 times and 7.6 times speedup, respectively, over an Intel Xeon software implementation.
BibTeX
@article{dai2014accelerating,
  author = {Wei Dai and Yarkin Doröz and Berk Sunar},
  title = {{Accelerating NTRU based Homomorphic Encryption using GPUs}},
  journal = {IACR Cryptol. ePrint Arch.},
  year = {2014},
}
Figure