International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
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
Download:
DOI: 10.13154/tches.v2018.i3.69-88
URL: https://tches.iacr.org/index.php/TCHES/article/view/7293
Search ePrint
Search Google
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 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.
BibTeX
@article{tches-2018-29050,
  title={Data Flow Oriented Hardware Design of RNS-based Polynomial Multiplication for SHE Acceleration},
  journal={IACR Trans. Cryptogr. Hardw. Embed. Syst.},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 3},
  pages={69-88},
  url={https://tches.iacr.org/index.php/TCHES/article/view/7293},
  doi={10.13154/tches.v2018.i3.69-88},
  author={Joël Cathébras and Alexandre Carbon and Peter Milder and Renaud Sirdey and Nicolas Ventroux},
  year=2018
}