ON THE POLYNOMIAL MULTIPLICATION ALGORITHMS FOR POST-QUANTUM CRYPTOGRAPHY

Abstract

Lattice-based systems work on polynomial rings. In post-quantum cryptography, polynomial rings of large degree are used to increase security. Among the operations performed on polynomial rings, the most time-consuming operation is multiplication. Therefore, various multiplication algorithms have been proposed to optimize the efficiency of newly developed systems. These algorithms generally aim to reduce the number of multiplications. Thus, the efficiency and cost of the systems are optimized. In this study, Toom-Cook, Karatsuba, NTT, TMVP algorithms are analyzed. Information about the number of reductions in multiplication numbers, their time complexity and the benefits they provide in systems are given. Bruun algorithm, which can be an alternative to the frequently used multiplication algorithms, is described in the method section. Among the polynomial multiplication algorithms, the NTT algorithm is considered to be the most efficient, so we have investigated its potential to increase efficiency. However, it is obvious that within certain criteria, TMVP and Bruun algorithm will provide an effective multiplication reduction in the system.

Keywords

• Lattice-based cryptography
• Polynomial multiplication algorithms
• Number theoretic transform
• Bruun algorithm

References

1. P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal on Computing 26 (5) (1997) 1484–1509.
2. G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson, D. Smith-Tone, Y.-K. Liu, Status report on the first round of the NIST post-quantum cryptography standardization process, National Institute for Standards and Technology Internal Report 8240, https://doi.org/10.6028/NIST. IR.8240 (2019).
3. D. Micciancio, O. Regev, Lattice-based cryptography, in: Post-quantum cryptography, Springer Berlin Heidelberg, 2009, pp. 147–191.
4. V. Hwang, A survey of polynomial multiplications for lattice-based cryptosystems, Cryptology ePrint Archive, Paper 2023/1962 (2023). URL https://eprint.iacr.org/2023/1962
5. J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, D. Stehle´, Crystals-kyber: a cca-secure module- lattice-based kem, in: 2018 IEEE European Symposium on Security and Privacy (EuroS&P), IEEE, 2018, pp. 353–367.
6. L. Ducas, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, D. Stehle´, Crystals–dilithium: Digital signatures from module lattices, Cryptology ePrint Archive (2018).
7. P. A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Prest, Z. Zhang, Falcon: Fast-fourier lattice-based compact signatures over NTRU, Submission to the NIST’s post-quantum cryptography standardization process 36 (5) (2018) 1–75.
8. R. T. Moenck, Practical fast polynomial multiplication, in: Proceedings of the third ACM symposium on Symbolic and algebraic computation, ACM, 1976, pp. 136–148.

9. D. Harvey, Faster arithmetic for number-theoretic transforms, Journal of Symbolic Computation 60 (2014) 113–119.
10. S. Winograd, On computing the discrete fourier transform, Mathematics of computation 32 (141) (1978) 175–199.
11. K. Derya, A. C. Mert, E. O¨ ztu¨rk, E. Savas¸, CoHA-NTT: A configurable hardware accelerator for NTT-based polynomial multiplication, Microprocessors and Microsystems 89 (2022). O. Toeplitz, Das algebraische analogon zu einem satze von feje´r, Mathematische Zeitschrift 2 (1) (1918) 187–197.
12. S. Ali, M. Cenk, Faster residue multiplication modulo 521-bit mersenne prime and an application to ECC, IEEE Transactions on Circuits and Systems I: Regular Papers 65 (8) (2018) 2477–2490.
13. M. A. Hasan, N. Meloni, A. H. Namin, C. Negre, Block recombination approach for subquadratic space complexity binary field multiplication based on toeplitz matrix-vector product, IEEE Transactions on Computers 61 (2) (2010) 151–163.
14. I. K. Paksoy, M. Cenk, TMVP-based multiplication for polynomial quotient rings and application to saber on ARM cortex-M4, cryptology ePrint Archive (2020).
15. S. Winograd, On multiplication of polynomials modulo a polynomial, SIAM Journal on Computing 9 (2) (1980) 225– 229.
16. G. Bruun, z-transform DFT filters and FFT’s, IEEE Transactions on Acoustics, Speech, and Signal Processing 26 (1) (1978) 56–63.
17. I. F. Blake, S. Gao, R. C. Mullin, Explicit factorization of x2k + 1 over Fp with prime p 3mod4, Applicable Algebra in Engineering, Communication and Computing 4 (2) (1993) 89–94.
18. H. W. Lenstra, Finding isomorphisms between finite fields, Mathematics of Computation 56 (193) (1991) 329–347.
19. V. Shoup, New algorithms for finding irreducible polynomials over finite fields, Mathematics of computation 54 (189) (1990) 435–447.
20. E. Yalc¸ın, F. Nuriyeva, E. Alkım, A comparative study on polynomial multiplication algorithms in context on post- quantum cryptography, in: DEU International Symposium Series on Graduate Researches-2022 DataScience, DEU, 2022, pp. 1–10.
21. M. Kannwischer, P. Bissmeyer, S. Schmidt, Optimizing lattice-based cryptography schemes with structured noise, in: Post-Quantum Cryptography: 5th International Conference, PQCrypto 2019, Fukuoka, Japan, July, Springer, 2019, pp. 81–97.
22. E. Alkim, V. Hwang, B.-Y. Yang, Multi-parameter support with ntts for ntru and ntru prime on cortex-m4, IACR Trans- actions on Cryptographic Hardware and Embedded Systems 2022 (4) (2022) 349–371.
23. I. K. Paksoy, M. Cenk, Faster ntru on arm cortex-m4 with tmvp-based multiplication, IEEE Transactions on Circuits and Systems I: Regular Papers 69 (10) (2022) 4083–4092.