  Homomorphic Encryption (HE) enables users to securely outsource both the
storage and computation of sensitive data to untrusted servers. Not only does
HE offer an attractive solution for security in cloud systems, but
lattice-based HE systems are also believed to be resistant to attacks by
quantum computers. However, current HE implementations suffer from
prohibitively high latency. For lattice-based HE to become viable for
real-world systems, it is necessary for the key bottlenecks - particularly
polynomial multiplication - to be highly efficient.
  In this paper, we present a characterization of GPU-based implementations of
polynomial multiplication. We begin with a survey of modular reduction
techniques and analyze several variants of the widely-used Barrett modular
reduction algorithm. We then propose a modular reduction variant optimized for
64-bit integer words on the GPU, obtaining a 1.8x speedup over the existing
comparable implementations. Next, we explore the following GPU-specific
improvements for polynomial multiplication targeted at optimizing latency and
throughput: 1) We present a 2D mixed-radix, multi-block implementation of NTT
that results in a 1.85x average speedup over the previous state-of-the-art. 2)
We explore shared memory optimizations aimed at reducing redundant memory
accesses, further improving speedups by 1.2x. 3) Finally, we fuse the Hadamard
product with neighboring stages of the NTT, reducing the twiddle factor memory
footprint by 50%. By combining our NTT optimizations, we achieve an overall
speedup of 123.13x and 2.37x over the previous state-of-the-art CPU and GPU
implementations of NTT kernels, respectively.
