Integer Based Fully Homomorphic DSP Accelerator using Weighted-Number Theoretic Transform

Abstract

Fully Homomorphic Encryption (FHE) has gained wide attention in cloud security as it allows computation on encrypted data. However, it requires a huge key size, resulting in impractical execution time. In this paper, we proposed an FHE hardware accelerator employing Weighted-Number Theoretic Transform (NTT) multiplier. NTT parameters are selected, in a way that the proposed design is executable on Digital Signal Processing (DSP) multiplier, to exploit its high clock rate. As the NTT kernel, is in general form, it can be pre-computed and stored in Look-up Tables (LUTs). The same LUTs are also usable for weight-factor as they both have symmetric periodicity properties. This optimization has saved 70% of LUTs utilization. Next optimization is proposed on reduction within NTT. The special prime moduli are exploited to accomplish a simple operation, where inverse Montgomery multiplication is replaced with shift and subtraction. The proposed optimizations are implemented for FHE encryption and realized on Kintex 7 platform. A magnitude of 93.2% speedup improvement is achieved for Toy, compared to benchmark software implementation. As the proposed design is targeted for full DSP implementation, it achieved a higher clock frequency (249.19 MHz), while consuming lower hardware resources.