Paper Info
Title
Hardware Architecture of a Number Theoretic Transform for a Bootstrappable RNS-based Homomorphic Encryption Scheme
Abstract
Homomorphic encryption (HE) is one of the most promising solutions to secure cloud computing. The number theoretic transform (NTT) that is widely used for convolution operations in HE requires a large amount of computation and has high parallelism, and therefore it has been a good candidate for hardware acceleration. Nevertheless, prior NTT hardware solutions for HE-based applications are impractical in most applications because they do not seriously consider the critical bootstrapping procedure that allows unlimited homomorphic operations on encrypted data. In this paper, we suggest practical bootstrappable parameters, specifically for an established residue number system (RNS)based HE scheme, and apply them to our NTT hardware design. In addition, to limit the size of internal memory for roots of unity increased by the bootstrappable parameters, only a few roots of unity are stored and others are generated on the fly. In our NTT hardware architecture, multiple NTT butterfly units (BUs) are efficiently deployed for high throughput and high resource utilization. In particular, several groups of BUs for respective moduli work in a parallel and pipelined manner, which is effective in an RNS-based HE scheme with a number of moduli. Our implementation on a Xilinx UltraScale FPGA with the bootstrappable parameters achieves a $118 \times$ faster processing speed than a software implementation, and it further provides various trade-off choices such as the number of DSP slices against BRAMs based on available FPGA resources.
Year
DOI
Venue
2020
10.1109/FCCM48280.2020.00017
2020 IEEE 28th Annual International Symposium on Field-Programmable Custom Computing Machines (FCCM)
Keywords
DocType
ISSN
hardware acceleration,HE-based applications,critical bootstrapping procedure,unlimited homomorphic operations,encrypted data,practical bootstrappable parameters,residue number system,NTT hardware design,NTT hardware architecture,multiple NTT butterfly units,high resource utilization,parallel manner,pipelined manner,number theoretic transform,bootstrappable RNS-based homomorphic encryption scheme,secure cloud computing,convolution operations,high parallelism,NTT hardware solutions
Conference
2576-2613
ISBN
Citations 
PageRank 
978-1-7281-5804-4
2
0.35
References 
Authors
16
6
Name
Order
Citations
PageRank
Sun-Woong Kim184.33
Keewoo Lee2163.02
Wonhee Cho343.09
Yujin Nam420.35
Jung Hee Cheon51787129.74
Rob A. Rutenbar62283280.48