A general split-ring number theory transformation

The number theoretical transformation (NTT) is widely recognized as the most efficient method for computing polynomial multiplication with high dimension and integral coefficients because of its quasilinear complexity.

What is the relationship between the NTT variants constructed by dividing the original polynomial into groups of lower-order subpolynomials such as K-NTT, H-NTT, and G3-NTT? Can they be viewed as special cases of a particular algorithm under different parameters?

To solve the problems, the research team led by Yunlei Zhao published New research On August 15, 2024 Frontiers of Computer Science.

The group proposed the first general split-ring number theory transformation, referred to as GSR-NTT. Then, they investigated the relationship between K-NTT, H-NTT and G3-NTT.

In the research, they investigate the generalized split-ring polynomial multiplication based on Monique increasing polynomial type, and they propose the first generalized split-ring number theory transformation, referred to as GSR-NTT. They demonstrate that K-NTT, H-NTT and G3-NTT can be considered special cases of GSR-NTT under different parameters.

They introduce a concise algorithm for complex analysis, based on which GSR-NTT can derive its optimal parameter settings. They provide other cases for GSR-NTD based on cyclic convolution based polynomials and three cyclotomic polynomials.

They use GSR-NTT to accelerate polynomial multiplication in a lattice-based scheme called NTTRU. Experimental results show that for NTTRU, GSR-NTT achieves a speedup of 24.7%, 37.6%, and 28.9% for key generation, concatenation, and decapsulation algorithms, respectively, leading to a total speedup of 29.4%.

Future work may focus on implementing GSR-NTT across multiple platforms.