Data Flow Oriented Hardware Design of RNS-based Polynomial Multiplication for SHE Acceleration

  • Joël Cathébras CEA, LIST, F-91191 Gif-sur-Yvette
  • Alexandre Carbon CEA, LIST, F-91191 Gif-sur-Yvette
  • Peter Milder Stony Brook University, Stony Brook, NY 11794-2350
  • Renaud Sirdey CEA, LIST, F-91191 Gif-sur-Yvette
  • Nicolas Ventroux CEA, LIST, F-91191 Gif-sur-Yvette
Keywords: Homomorphic Encryption, Polynomial Multiplication, Residue Number System, Negative Wrapped Convolution, Hardware Implementation


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 Mult&Relin 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.

How to Cite
Cathébras, J., Carbon, A., Milder, P., Sirdey, R., & Ventroux, N. (2018). Data Flow Oriented Hardware Design of RNS-based Polynomial Multiplication for SHE Acceleration. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(3), 69-88.