Homomorphic encryption (HE) has emerged as an ideal cryptographic technology for meaningful computations on encrypted data. Not only does HE secure private information even if the ciphertext is leaked, but it also maintains data integrity when inferring cloud-side services. However, homomorphic computations include expensive polynomial arithmetic, especially polynomial multiplication. Prior studies proposed number theoretic transform (NTT) hardware designs to accelerate polynomial multiplication. However, the trade-off between hardware complexity and throughput of NTT designs was not considered carefully. This paper proposes an area-efficient NTT architecture suitable for HE schemes. Center of the proposed NTT architecture is a high-throughput butterfly unit array, which communicates with a single data memory unit through a conflict-free memory access pattern. Additionally, we developed a twiddle factor generator to reduce memory consumption. The proposed NTT architecture was successfully accelerated on the Xilinx FPGA devices. Performing with a large number of moduli, the proposed NTT design achieves higher hardware efficiency than the prior arts. Especially, our NTT design consumes less on-chip memory with efficiency improvement of $8.8\times $ over the most related work. The implementation results confirm that our design methodology has advantages to deploy many NTT accelerators on an FPGA device for practical HE-based applications.
With the increasing number of edge devices connecting to the cloud for storage and analysis, concerns about security and data privacy have become more prominent. Homomorphic encryption (HE) provides a promising solution by not only preserving data privacy but also enabling meaningful computations on encrypted data; while considerable efforts have been devoted to accelerating expensive homomorphic evaluation in the cloud, little attention has been paid to optimizing encryption and decryption (ENC-DEC) operations on the edge. In this paper, we propose efficient hardware architectures for CKKS-based ENC-DEC accelerators to facilitate computations on the client side. The proposed architectures are configurable to support a wide range of polynomial sizes with multiplicative depths (up to 30 levels) at a 128-bit security guarantee. We evaluate the hardware designs on the Xilinx XCU250 FPGA platform and achieve an average encryption time 23.7× faster than that of the well-known SEAL HE library. By reducing time complexity and improving the hardware utilization of cryptographic algorithms, our configurable CKKS-supported ENC-DEC hardware designs have the potential to greatly accelerate cryptographic processes on the client side in the post-quantum era.
26 June 2023 in IEEE Transactions on Circuits and Systems II: Express Briefs
Fully Homomorphic Encryption (FHE) is currently seen to be a promising solution for privacy-preserving applications. However, FHE suffers from a computational bottleneck due to the need to perform large polynomial calculations. Number Theoretic Transform (NTT) as a fundamental component of FHE is widely used to reduce latency and computation complexity while performing polynomial multiplication. Designing FHE can be challenging because it requires different settings depending on the application, such as the polynomial degree and coefficient modulus size. The hardware design has to stick to specific parameter values, which can make things harder to be implemented. In this brief, we present a configurable hardware accelerator for NTT that supports a wide range of parameter settings without any recompilation. This module is highly parallelized and designed for high throughput on the butterfly unit array. We provide a conflict-free access memory between the NTT Core and memory to increase performance. For the evaluation, our NTT and INTT modules show significant performance improvements compared to the CPU implementation using Microsoft’s SEAL 4.0 library by factors of $8.88\times $ and $11.2\times $ , respectively. In comparison with the state-of-the-art hardware implementation, our module showed better performance with $1.46\times $ improvement of throughput/slice metric as a fair comparison while consuming fewer hardware resources.
Lattice-based cryptography continues to dominate in the second-round finalists of the National Institute of Standards and Technology post-quantum cryptography standardization process. Computational efficiency is primarily considered to evaluate promising candidates for final round selection. In lattice-based cryptosystems, polynomial multiplication is the most expensive computation and critical to improve the performance. This paper proposes an efficient number theoretic transform (NTT) architecture to accelerate the polynomial multiplication. The proposed design applies mixed-radix multi-path delay feedback architecture and flexibly adopts various polynomial sizes. Configurable NTT design is realized to perform forward and inverse NTT computations on a unified hardware, which is then used to develop an efficient polynomial multiplier. The proposed architectures were successfully accelerated on several Xilinx FPGA platforms to directly compare with state-of-the-art works. The implementation results show that the proposed NTT architectures have comparable area-time product and demonstrate $1.7\sim 17\times $ performance improvement, and the proposed polynomial multipliers achieve higher performance compared with previous works. Experimental results confirmed the proposed design’s applicability for high-speed large-scale data cryptoprocessors.
Fully homomorphic encryption (FHE) provides a solution to privacy-preserving applications because of its ability to perform computations on encrypted data without exposing raw data. However, FHE suffers from implementation bottlenecks owing to the large computations involved, particularly with bootstrapping. Bootstrapping is necessary in FHE to enable an unlimited number of multiplication. Nonetheless, implementing bootstrapping requires a significantly large polynomial length, $N=2^{16}$ or 217, to considerably secure the system. Thus, polynomial multiplication will be challenging in terms of resources and time. This problem can be resolved by implementing the number theoretic transform (NTT) that can perform polynomial multiplication in quasi-linear complexity. However, designing an NTT architecture for FHE is challenging because it requires various parameters, particularly the high polynomial degree that will require a considerable amount of hardware resources and clock latency. This study proposes a design for FPGA implementation of the NTT architecture with flexible input lengths: 216 and 217 by combining radix-2 and radix-24. Twiddle factor generator (TFG) and efficient configurable modular multiplication (MM) unit are also utilized to achieve time and area-efficient architecture. The proposed design was synthesized on the FPGA Xilinx ALVEO U250 and demonstrated higher hardware efficiency and optimum latency that outperforms those reported in previous studies.
28 September 2023 in IEEE Transactions on Circuits and Systems I: Regular Papers
The CRYSTALS-Dilithium protocol is considered as one of the most promising digital signature schemes in NIST’s post-quantum cryptography standardization process. While separating arithmetic computation units can be advantageous in some cases, it can lead to increased hardware resource consumption and performance degradation. To overcome this issue, this paper proposes a novel architecture called the Unified Polynomial Arithmetic Unit (UniPAU), specifically designed for the Dilithium signature scheme. The proposed UniPAU offers a unique hardware module that can execute all the polynomial operations required for the Dilithium signature scheme. To demonstrate the effectiveness of our design, we implemented it on the Xilinx Zynq UltraScale+ ZCU102 (xczu9eg-ffvb1156-2-e) FPGA platform and evaluated its hardware efficiency and performance. Our implementation results indicate that the proposed UniPAU can achieve comparable throughput while consuming fewer hardware resources compared to state-of-the-art studies. These findings suggest that our UniPAU can provide an optimized and efficient hardware solution for polynomial arithmetic operations in the Dilithium signature scheme.