The design space of the number theoretic transform: A survey

Felipe Valencia, Ayesha Khalid, Elizabeth O'Sullivan, Francesco Regazzoni

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Citations (Scopus)

Abstract

The Number Theoretic Transform (NTT) is a necessary part of most Lattice-based cryptographic schemes. In particular, it offers an efficient means to achieve polynomial multiplication within the more efficient ring-based schemes. The NTT is also a crucial component which needs to be implemented in a critical way, since it is often the bottle-neck and the most resource consuming block of the whole design. As a result, the NTT is an appealing target for exploring different architectures and design trade-offs. In this paper, we compare various optimization strategies applied to maximize the performance or to reduce the resource utilization. Our analysis covers general purpose processors as well as dedicated hardware implemented on reconfigurable platforms and on ASIC. Previously explored design strategies range from the traditional computation where the multiplicative factors (called twiddle factors) are calculated on-the-fly versus memory trade-off exploration (using memory to store pre-computed twiddle factors), to the use of different butterfly designs for implementing the Fast Fourier Transform and its inverse in software, or the sharing of resources for hardware implementations of the forward and inverse NTT. The problem of side channel resistance is also addressed, discussing designs which are robust against power analysis attacks.

Original languageEnglish
Title of host publication17th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS 2017): Proceedings
EditorsYale Patt, S. K. Nandy
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages273-277
Number of pages5
Volume2018-January
ISBN (Electronic)9781538634370
ISBN (Print)978-1-5386-3438-7
DOIs
Publication statusPublished - 23 Apr 2018
Event17th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS 2017 - Samos, Greece
Duration: 16 Jul 201720 Jul 2017

Conference

Conference17th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation, SAMOS 2017
CountryGreece
CitySamos
Period16/07/201720/07/2017

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Hardware and Architecture
  • Modelling and Simulation

Fingerprint Dive into the research topics of 'The design space of the number theoretic transform: A survey'. Together they form a unique fingerprint.

  • Cite this

    Valencia, F., Khalid, A., O'Sullivan, E., & Regazzoni, F. (2018). The design space of the number theoretic transform: A survey. In Y. Patt, & S. K. Nandy (Eds.), 17th International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS 2017): Proceedings (Vol. 2018-January, pp. 273-277). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/SAMOS.2017.8344640