Paper Info
Title
Data Flow Oriented Hardware Design of RNS-based Polynomial Multiplication for SHE Acceleration.
Abstract
This paper presents a hardware implementation of a Residue Polynomial Multiplier (RPM), designed to accelerate the full Residue Number System (RNS) variant of the Fan-Vercauteren scheme proposed by Bajard et al. [BEHZ16]. Our design speeds up polynomial multiplication via a Negative Wrapped Convolution (NWC) which locally computes the required RNS channel dependent twiddle factors. Compared to related works, this design is more versatile regarding the addressable parameter sets for the BFV scheme. This is mainly brought by our proposed twiddle factor generator that makes the design BRAM utilization independent of the RNS basis size, with a negligible communication bandwidth usage for non-payload data. Furthermore, the generalization of a DFT hardware generator is explored in order to generate RNS friendly NTT architectures. This approach helps us to validate our RPM design over parameter sets from the work of Halevi et al. [HPS18]. For the depth-20 setting, we achieve an estimated speed up for the residue polynomial multiplications greater than 76 during ciphertexts multiplication, and greater than 16 during relinearization. It thus results in a single-threaded Multu0026Relin ciphertext operation in 109.4 ms (×3.19 faster than [HPS18]) with RPM counting for less than 15% of the new computation time. Our RPM design scales up with reasonable use of hardware resources and realistic bandwidth requirements. It can also be exploited for other RNS based implementations of RLWE cryptosystems.
Year
Venue
Field
2018
IACR Trans. Cryptogr. Hardw. Embed. Syst.
Polynomial,Convolution,Computer science,Twiddle factor,Multiplier (economics),Multiplication,Bandwidth (signal processing),Residue number system,Computer hardware,Speedup
DocType
Volume
Issue
Journal
2018
3
Citations 
PageRank 
References 
0
0.34
0
Authors
5
Name
Order
Citations
PageRank
Joël Cathébras100.34
Alexandre Carbon221.78
Peter Milder334628.41
Renaud Sirdey417526.73
N. Ventroux59913.59