A fast NTRU software implementation based on 5-way TMVP

Yaman Gökce N., Gökce A. B., CENK M.

Journal of Information Security and Applications, cilt.81, 2024 (SCI-Expanded) identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 81
  • Basım Tarihi: 2024
  • Doi Numarası: 10.1016/j.jisa.2023.103688
  • Dergi Adı: Journal of Information Security and Applications
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Anahtar Kelimeler: Lattice-based cryptography, NTRU, Polynomial multiplication, Post-quantum cryptography, TMVP, Toeplitz matrices
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

The fast and efficient operation of post-quantum cryptographic algorithms has become an important research topic, especially with the recent developments and the process of the PQC Standardization Project by NIST. Various algorithms based on lattices are chosen to be finalists in this project. Number Theoretic Transform (NTT), Toom–Cook, Karatsuba, and Toeplitz matrix–vector product (TMVP) are considered in order to efficiently perform multiplications in quotient polynomial rings required by the cryptographic schemes based on lattices. In this paper, we propose a 5-way split TMVP-based algorithm for multiplication in polynomial quotient rings and determine its computational complexity. The new algorithm is derived from a 5-term polynomial multiplication algorithm using 13 multiplications with coefficients of only 1 or -1 that provide efficiency. We also implement it for all parameter sets of NTRU. The results show that we have up to 34%, 35%, and 157% speed-up against Toom4-Karatsuba implementation in key generation, encapsulation, and decapsulation, respectively.