Area-Time Product Efficient RNS Polynomial Base Extension On FPGA

Homomorphic Encryption (HE) allows us to perform privacy-preserving processingof data by computing on ciphertexts. Using HE can eliminate the trust required tooffload computation to third parties that have more scalable computational power.A barrier to adopting HE in more practical processing of data is its inherent computationalcomplexity. Current HE schemes such as Brakerski-Fan-Vercauteren (BFV)can be accelerated through loosely coupled accelerator devices to accommodate theperformance requirements of even more applications. Developing an accelerator forHE requires implementation of algorithms that have irregular memory accesses, suchas Number Theoretic Transform (NTT). Even after accelerating the NTT algorithm,the communication overhead between the host and the device offsets some of thebenefits of this acceleration. To achieve further performance gains, the implementationof a larger set of arithmetic operations is required. One such operation isbase extension, needed when the Residue Number System (RNS) is utilized to performefficient arithmetic of larger integers. For example, the modulus used for theciphertext Q is chosen as 1747-bits to satisfy the 128-bit security level with ringdimension N = 216. Utilizing RNS, we can choose 28×64-bit primes or 55×32-bitprimes to satisfy the required parameters. During homomorphic multiplication, ourresults may not fit within the range afforded by the current RNS base. Then, a baseextension is required before the operation to increase the representation range. Ina complete HE accelerator, the NTT unit produces residues that will be consumedby the base extension unit and vice versa to compute homomorphic multiplicationoperations on the accelerator device. By not communicating back to the host, thedata movement overheads will be avoided. Our base extension implementation is optimized for its Area-Time Product (ATP) metric for HE accelerators that havemultiple units competing for device programmable logic area. We present a compiletimeconfigurable hardware generator for exact base extension with parameters forthe available memory bandwidth on the device. The design features a scalable architecturethat decouples performance from the underlying base extension arithmetic.A compile-time tunable throughput parameter can increase the performance of theoperation at the cost of additional logic area. We provide our Field ProgrammableGate Array (FPGA) utilization results for ring sizes from 212 to 216. We compareour base extension architecture to architectures available in the literature. Wedemonstrate comparisons with the state-of-the-art open source HE software libraryOpenFHE against our FPGA implementation and show that our implementationachieves a ×10−17 speedup over the software implem