Generalized splitting-ring number theoretic transform

Graphical abstract

References

[1] Pollard J M . The fast Fourier transform in a finite field. Mathematics of Computation, 1971, 25( 114): 365–374

[2] Agarwal R C, Burrus C S . Number theoretic transforms to implement fast digital convolution. Proceedings of the IEEE, 1975, 63( 4): 550–560

[3] Zhu Y M, Liu Z, Pan Y B. When NTT meets Karatsuba: preprocess-then-NTT technique revisited. In: Proceedings of the 23rd International Conference on Information and Communications Security. 2021, 249−264

[4] Liang Z C, Shen S Y, Shi Y T, Sun D N, Zhang C X, Zhang G Y, Zhao Y L, Zhao Z X. Number theoretic transform: generalization, optimization, concrete analysis and applications. In: Proceedings of the 16th International Conference on Information Security and Cryptology. 2020, 415−432

[5] Lyubashevsky V, Seiler G . NTTRU: truly fast NTRU using NTT. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2019, 2019( 3): 180–201

[6] Nussbaumer H . Fast polynomial transform algorithms for digital convolution. IEEE Transactions on Acoustics, Speech, and Signal Processing, 1980, 28( 2): 205–215

[7] Hassan C A, Yayla O. Radix-3 NTT-based polynomial multiplication for lattice-based cryptography. IACR Cryptology ePrint Archive, 2022, 726

Acknowledgements

This work was supported by the National Natural Science Foundation of China (Grant No. 61877011), the National Key Research and Development Program of China (No. 2022YFB2701600), the Shanghai Science and Technology Innovation Action Plan (No. 21DZ2200500), and the Shandong Provincial Key Research and Development Program of China (Nos. 2017CXG0701 and 2018CXGC0701).

Competing interests

The authors declare that they have no competing interests or financial conflicts to disclose.

RIGHTS & PERMISSIONS

2024 Higher Education Press