Designing an FPGA-Accelerated Homomorphic Encryption Co-Processor

In this paper we report on our advances designing and implementing an FPGA-based computation accelerator as part of a Homomorphic Encryption Processing Unit (HEPU) co-processor. This hardware accelerator technology improves the practicality of computing on encrypted data by reducing the computational bottlenecks of lattice encryption primitives that support homomorphic encryption schemes. We focus on accelerating the Chinese Remainder Transform (CRT) and inverse Chinese Remainder Transform (iCRT) for power-of-2 cyclotomic rings, but also accelerate other basic ring arithmetic such as Ring Addition, Ring Subtraction and Ring Multiplication. We instantiate this capability in a Xilinx Virtex-7 FPGA that can attach to a host computer through either a PCI-Express port or Ethernet. We focus our experimental performance analysis on the NTRU-based LTV Homomorphic Encryption scheme. This is a leveled homomorphic encryption scheme, but our accelerator is compatible with other lattice-based schemes and recent improved bootstrapping designs to support arbitrary depth computation. We experimentally compare performance with a reference software implementations of the CRT and iCRT bottlenecks and when used in a practical application of encrypted string comparison.

I. Introduction

Recent advances in lattice-based Homomorphic Encryption (HE) have shown that it can be practical to securely run arbitrary computations over encrypted data [1], [2]. In addition to supporting encrypted computing, lattice-based HE schemes are attractive because they are post-quantum public-key schemes [3], meaning they are resistant to quantum computing attacks. Despite recent advances, HE is still not widely practical, partially because of computational bottlenecks in lattice-based HE schemes when run on commodity CPU-based computation devices. It would be valuable to accelerate the execution of core HE operations, possibly in a low-cost but computationally efficient and highly optimized hardware co-processor.