The ring learning with error (RLWE)-based fully homomorphic encryption (FHE) scheme has become one of the most promising FHE schemes. However, its performance is limited by the homomorphic multiplication, especially the polynomial multiplication which occupies major computing resources. Therefore, efficient implementation of polynomial multiplication is crucial for high-performance FHE applications. In this article, we present an area-efficient and highly unified reconfigurable multicore number theoretic transform (NTT)/inverse NTT (INTT) architecture (named MCNA), which employs NTT and INTT for polynomial multiplier with a variable number of reconfigurable processing elements. To reduce latency, MCNA merges the preprocessing and postprocessing into the constant-geometry NTT and INTT, respectively. Also, a reconfigurable modular multiplier based on digital signal processor (DSP) is proposed to speed up the modular multiplication. In order to avoid designing independent memory access pattern for INTT, a unified read/write structure of NTT/INTT is presented. Furthermore, a novel memory access pattern named “cyclic-sharing” is proposed to reduce 25% memory capacity. MCNA is evaluated on a Xilinx Virtex-7 field-programmable gate array (FPGA) platform. Running at 250-MHz clock frequency, the throughput of MCNA for NTT/INTT achieves $2.78\times \sim 9.32\times $ improvements in comparison to prior works, while the area efficiency of lookup table (LUT) and flip-flop (FF) is improved by $1.25\times \sim 4.79\times $ . For polynomial multiplication, the throughput of MCNA achieves $3.73\times \sim 7.69\times $ enhancements, as well as $1.13\times \sim 14.8\times $ area efficiency improvements.

Fully homomorphic encryption (FHE) allows arbitrary computation on encrypted data and has great potential in privacy-preserving cloud computing and securely outsource computational tasks. However, the excessive computation complexity is the key limitation that restricting the practical application of FHE. In this paper we proposed a FPGA-based high parallelism architecture to accelerate the FHE schemes based on the ring learning with errors (RLWE) problem, specifically, we presented a fast implementation of leveled fully homomorphic encryption scheme BGV. In order to reduce the computation latency and improve the performance, we applied both circuit-level and block-level pipeline strategies to improve clock frequency, and as a result, enhance the processing speed of polynomial multipliers and homomorphic evaluation functions. At the same time, multiple polynomial multipliers and modular reduction units were deployed in parallel to further improve the hardware performance. Finally, we implemented and tested our architecture on a Virtex UltraScale FPGA platform. Runing at 150MHz, our implementation achieved 4.60x~9.49x speedup with respect to the optimized software implementation on Intel i7 processor running at 3.1GHz for homomorphic encryption and decryption, and the throughput was increased by 1.03x~4.64x compared to the hardware implementation of BGV. While compared to the hardware implementation of FV, the throughput of our accelerator also achieved 5.05x and 167.3x speedup for homomorphic addition and homomorphic multiplication operation respectively.

Fully homomorphic encryption (FHE) allows arbitrary computation on encrypted data and thus has potential in privacy-preserving computing. However, efficiency is still the bottleneck. In this paper we present an area-efficient and highly unified reconfigurable multi-core architecture (named ReMCA) for full Residue Number System (RNS) variant of Fan-Vercauteren variant of Brakerski’s scheme (RNS-BFV), which employs a variable number of reconfigurable processing elements (PEs) and RNS channels. The PE unit can be flexibly configured as NTT, INTT or modular multiplier, thereby avoiding the need of other extra computational units. To reduce the computational complexity, ReMCA merges the pre/post-processing into NTT/INTT and unifies the read/write structure of NTT and INTT. Also, a conflict-free memory access pattern that doesn’t need separate bit-reversal operation is proposed to optimize the memory access. Furthermore, targeting different computational requirements, a unified hardware architecture mapping model and data memory organization model are introduced, and all the computing units that RNS-BFV involved are optimized and mapped on ReMCA. ReMCA is evaluated on a Xilinx Virtex-7 FPGA platform. Running at 250MHz, it can perform 2260 homomorphic multiplication per second. When normalized to the same parameter set, the throughput and Area-Time-Products (ATPs) of ReMCA achieve $1.45\times \sim 5.51\times $ and $1.58\times \sim 5.12\times $ improvements.

Polynomial multiplication over rings is a significant bottleneck of ring learning with error (RLWE)-based encryption. To speed it up, three algorithms are widely used, i.e., number theoretic transform (NTT), Schoolbook, and Toom-Cook. Compared with Schoolbook and NTT, Toom-Cook can achieve a better trade-off between performance and flexibility. However, in Toom-Cook postprocessing, there are many redundant steps and calculations that have not been eliminated. Therefore, we propose an efficient, compressed, and fused Toom-Cook postprocessing algorithm that reduces the number of steps and at least 33.33% of the arithmetic operations of postprocessing. A highly reconfigurable and efficient Toom-Cook-based polynomial multiplier (TCPM) is proposed to speed up polynomial multiplication over rings. In TCPM, a high-throughput and efficient heterogeneous processing element (PE) array is designed to exploit the parallelism of Toom-Cook, and based on the compressed algorithm, the PE array for postprocessing is scaled down. In addition, as it is provided with a reconfigurable evaluation module, a flexible polynomial data storage module and a universal PE array, TCPM can efficiently map and execute Toom-Cook-2, 3, and 4 on a unified hardware architecture. Implemented on the Xilinx VC709 field-programmable gate array (FPGA) platform, TCPM can perform a Toom-Cook-4-based 256 $\times$ 256 polynomial multiplication over rings with a modulus of a power of two or a prime every 3.28 $\mu$ s at a 360-MHz clock frequency. It achieves a 2.47 $\times$ to 50.11 $\times$ speedup compared with the previous designs.

Polynomial multiplication over rings is a significant bottleneck of ring learning with error (RLWE)-based encryption. To speed it up, the number theoretic transform (NTT) and Toom-Cook-4 (TC4) are commonly used algorithms. Compared with NTT, TC4 is less restrictive and more flexible. However, there is a large opportunity at the algorithm level to improve the Schoolbook algorithm and postprocessing of TC4. Therefore, we propose a novel and efficient Winograd-Schoolbook algorithm that reduces multiplication by 29.1% (N $=$ 256). We also propose a fused and low-density postprocessing that simplifies the algorithm flow and reduces multiplication by 56.25%. In total, these two-part improvements reduce the multiplication of TC4 by 32.47%. A high throughput and efficiency TC4 polynomial multiplier (TCMW) is proposed to speed up polynomial multiplication over rings. In TCMW, a highly parallel full pipelined structure without data waiting between modules is designed to make the parallelism of each module match and avoid the storage of intermediate results. In addition, based on the improved TC4, data buffers with data reuse, elementwise vector multiplication (EWVM) arrays, and efficient interpolation arrays are all designed to improve the performance and efficiency of TCMW. Implemented on the Xilinx VC709 field programmable gate array (FPGA) platform, TCMW can perform a TC4-based $256\times 256$ polynomial multiplication over rings with an unrestricted modulus (as long as its factors do not contain 3 or 5) every 1.89 $\mu$ s at a 385 MHz clock frequency. Compared with prior designs of TC4, under the same conditions, the throughput of TCMW achieves an improvement of 1.91 $\times$ $\sim$ 7.71 $\times$ , and the efficiency of LUT and DSP achieve improvements of 1.31 $\times$ $\sim$ 3.67 $\times$ and 1.87 $\times$ $\sim$ 4.92 $\times$ , respectively.

To accelerate RNS-CKKS, little attention is paid to the acceleration of the operations on the edge-client. However, the devices used by the edge-client are often low-end and have limited resources and computing power, so the performance of RNS-CKKS encoding, decoding, encryption and decryption also needs to be improved. Consequently, we propose a compact and efficient hardware accelerator architecture named CAEA for these operations. In order to improve the compactness of CAEA, a reconfigurable butterfly unit is proposed, which considers both complex number arithmetic and integer modular arithmetic, so that FFT/IFFT and NTT/INTT can be executed on unified hardware processing elements without additional resource and waste. Moreover, in order to improve the computational efficiency, we also improved the dataflow of encoding, decoding, encryption, and decryption on CAEA to reduce the number of required operations and latency. CAEA is synthesized based on SMIC 40nm technology, and is also implemented on Xilinx Kintex-7 and Zynq UltraScale+ FPGA. Compared with the prior related works, in terms of performance, CAEA can achieve $2.01\times $ speedup for encoding and decoding, $1.13\times \sim ~87.86\times $ speedup for encryption, and $3.03\times \sim ~69.64\times $ speedup for decryption. Compared with the state-of-the-art work, CAEA can achieve $1.06\times \sim ~4.96\times $ improvement in terms of area efficiency.