An extensive study of flexible design methods for the number theoretic transform

Mert, Ahmet Can and Karabulut, Emre and Öztürk, Erdinç and Savaş, Erkay and Aysu, Aydın (2020) An extensive study of flexible design methods for the number theoretic transform. IEEE Transactions on Computers . ISSN 0018-9340 (Print) 1557-9956 (Online) Published Online First http://dx.doi.org/10.1109/TC.2020.3017930

Warning
There is a more recent version of this item available.
[thumbnail of 09171507.pdf] PDF
09171507.pdf
Restricted to Registered users only

Download (7MB) | Request a copy

Abstract

Efficient lattice-based cryptosystems operate with polynomial rings with the Number Theoretic Transform (NTT) to reduce the computational complexity of polynomial multiplication. NTT has therefore become a major arithmetic component (thus computational bottleneck) in various cryptographic constructions like hash functions, key-encapsulation mechanisms, digital signatures, and homomorphic encryption. Although there exist several hardware designs in prior work for NTT, they all are isolated design instances fixed for specific NTT parameters or parallelization level. This paper provides an extensive study of flexible design methods for NTT implementation. To that end, we evaluate three cases: (1) parametric hardware design, (2) high-level synthesis (HLS) design approach, (3) and design for software implementation compiled on soft-core processors, where all are targeted on reconfigurable hardware devices. We evaluate the designs that implement multiple NTT parameters and/or processing elements, demonstrate the design details for each case, and provide a fair comparison with each other and prior work. On a Xilinx Virtex-7 FPGA, compared to HLS and processor-based methods, the results show that the parametric hardware design is on average 4.4x and 73.9x smaller and 22.5x and 19.3x faster, respectively. Surprisingly, HLS tools can yield less efficient solutions than processor-based approaches in some cases.
Item Type: Article
Subjects: T Technology > TK Electrical engineering. Electronics Nuclear engineering > TK7800-8360 Electronics > TK7885-7895 Computer engineering. Computer hardware
Q Science > QA Mathematics > QA075 Electronic computers. Computer science
Divisions: Faculty of Engineering and Natural Sciences > Academic programs > Computer Science & Eng.
Faculty of Engineering and Natural Sciences > Academic programs > Electronics
Faculty of Engineering and Natural Sciences
Depositing User: Erkay Savaş
Date Deposited: 22 Sep 2020 15:18
Last Modified: 22 Sep 2020 15:18
URI: https://research.sabanciuniv.edu/id/eprint/40593

Available Versions of this Item

Actions (login required)

View Item
View Item