LHF-NTT: Local Horizontal Folding Number Theoretic Transform Hardware Accelerator

IEEE International System-on-Chip Conference (SOCC), pp. 1–6

Abstract

Polynomial multiplications in lattice-based cryptography (LBC) can be addressed by number theoretic transform (NTT). To accelerate NTT in hardware, the memory-based architecture is very popular, with butterfly processing elements (PEs) arranged in a 1-dimensional vector (1D) or a 2-dimensional (2D) systolic array. With the growing need to keep data secure and the potential of quantum computers, the demand for energy efficient and high throughput operation is rising. Building on the extensive research in this field, a new systolic vector architecture is proposed in this work, namely the local horizontal folding NTT (LHF-NTT). Unlike forward feeding of data among PEs in the systolic array, the proposed systolic vector locally feeds the output data of PEs back to their input. On one hand, the memory bottleneck is addressed by requiring fewer memory accesses, which also reduce energy consumption. On the other hand, this increase in computational intensity can be used to instantiate more efficient memories of fewer banks, or to increase throughput with more PEs while relying on a classic split into memory banks. The proposed LHF-NTT outperforms 1D-NTT by reducing memory accesses by at least 50% at the same throughput and PE count. In the case of 2D-NTT, the throughput can be doubled while keeping the memory bandwidth unchanged.

Authors 2

1. Shutao Zhang Aachen Chair of Integrated Digital Systems and Circuit Design (IDS)

   RWTH Aachen University

   Affiliation as printed

   Chair of Integrated Digital Systems and Circuit Design, RWTH Aachen University,Germany

2. Tobias Gemmeke Aachen Chair of Integrated Digital Systems and Circuit Design (IDS)

   RWTH Aachen University

   Affiliation as printed

   Chair of Integrated Digital Systems and Circuit Design, RWTH Aachen University,Germany