Binary Subscript Representation and Efficient Pipelined Number Theoretic Transform

Recommended citation: Binary Subscript Representation and Efficient Pipelined Number Theoretic Transform. Bo Zhang, Mingzhe Zhang, Shoumeng Yan. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems (TCAD).

Abstract

As a key operation, the number theoretic transform (NTT) has a significant impact on the performance of emerging cryptosystems, such as fully homomorphic encryption. To better explain NTT algorithms with arbitrary size, radix, order, etc., we introduce the binary subscript representation (BSR), presented by a series of binary strings based on input and output subscripts. By proving bit exchanges of subscripts and the lifespan of twiddle factors, BSR enables a rapid understanding of data flow within each stage and every multiplication, thereby describing how NTT algorithms transform input coefficients into output coefficients. After exploring the design space described by BSR, we propose a pipelined NTT algorithm, possessing the abilities to (i) support NTT and inverse NTT at run-time without internal data rerouting nor external data reordering, (ii) reduce the memory storage of twiddle factors by roughly 50%, (iii) simplify most of the modular multiplications as Shoup modular multiplications, (iv) optimize the modular division over coefficient size N. Later, we implement the algorithm on two pipelined architectures: serial commutator (SC) and multi-path delay commutator (MDC). Along with $2^{12}/2^{14}$ coefficients and 32/64-bit modulus, we totally generate 8 NTT designs. Experimental results demonstrate the advantages of our proposed NTT. For instance, our proposed $2^{12}$-coefficient 64-bit MDC NTT saves 63.74% area/throughput, compared with state-of-art designs.

Abstract source