Design and implementation of a fast and scalable NTT-based polynomial multiplier architecture

Mert, Ahmet Can and Öztürk, Erdinç and Savaş, Erkay (2019) Design and implementation of a fast and scalable NTT-based polynomial multiplier architecture. In: 2019 Euromicro Conference on Digital System Design (DSD), Kallithea, Greece (Accepted/In Press)

PDF (Design and Implementation of a Fast and Scalable NTT-Based Polynomial Multiplier Architecture) - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


In this paper, we present an optimized FPGA implementation of a novel, fast and highly parallelized NTT-based polynomial multiplier architecture, which proves to be effective as an accelerator for lattice-based homomorphic cryptographic schemes. As I/O operations are as time-consuming as NTT operations during homomorphic computations in a host processor/accelerator setting, instead of achieving the fastest NTT implementation possible on the target FPGA, we focus on a balanced time performance between the NTT and I/O operations. Even with this goal, we achieved the fastest NTT implementation in literature, to the best of our knowledge. For proof of concept, we utilize our architecture in a framework for Fan-Vercauteren (FV) homomorphic encryption scheme, utilizing a hardware/software co-design approach, in which polynomial multiplication operations are offloaded to the accelerator via PCIe bus while the rest of operations in the FV scheme are executed in software running on an off-the-shelf desktop computer. Specifically, our framework is optimized to accelerate Simple Encrypted Arithmetic Library (SEAL), developed by the Cryptography Research Group at Microsoft Research, for the FV encryption scheme, where large degree polynomial multiplications are utilized extensively. The hardware part of the proposed framework targets Xilinx Virtex-7 FPGA device and the proposed framework achieves almost 11x latency speedup for the offloaded operations compared to their pure software implementations.

Item Type:Papers in Conference Proceedings
ID Code:37407
Deposited By:Ahmet Can Mert
Deposited On:04 Aug 2019 23:27
Last Modified:04 Aug 2019 23:27

Repository Staff Only: item control page