Faster characteristic three polynomial multiplication and its application to NTRU Prime decapsulation

Yeniaras E., CENK M.

JOURNAL OF CRYPTOGRAPHIC ENGINEERING, cilt.12, sa.3, ss.329-348, 2022 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 12 Sayı: 3
  • Basım Tarihi: 2022
  • Doi Numarası: 10.1007/s13389-021-00282-7
  • Dergi Adı: JOURNAL OF CRYPTOGRAPHIC ENGINEERING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Emerging Sources Citation Index (ESCI), Scopus, Compendex, INSPEC
  • Sayfa Sayıları: ss.329-348
  • Anahtar Kelimeler: Characteristic three fields, Karatsuba, Key encapsulation, Lattice-based cryptography, NTRU Prime, Polynomial multiplication, Post-quantum cryptography, DISCRETE LOGARITHMS, ALGORITHMS, FORMULAS, FIELDS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

Efficient computation of polynomial multiplication over characteristic three fields is required for post-quantum cryptographic applications which gain importance upon the recent advances in quantum computers. In this paper, we propose three new polynomial multiplication algorithms over F-3 and show that they are more efficient than the current state-of-the-art algorithms. We first examine through the well-known multiplication algorithms in F-3[x] including the Karatsuba 2-way and 3-way split formulas along with the latest enhancements. Then, we propose a new 4-way split polynomial multiplication algorithm and an improved version of it which are both derived by using interpolation in F-9, the finite field with nine elements. Moreover, we propose a 5-way split multiplication algorithm and then compare the efficiencies of these algorithms altogether. Even though there exist 4-way or 5-way split multiplication algorithms in characteristic two (binary) fields, there has not been any such algorithms developed for characteristic three fields before this paper. We apply the proposed algorithms to the NTRU Prime protocol, a post-quantum key encapsulation mechanism, submitted to the MST PQC Competition by Bernstein et al., performing polynomial multiplication over characteristic three fields in its decapsulation phase. We observe that the new hybrid algorithms provide a 12.9% reduction in the arithmetic complexity. Furthermore, we implement these new hybrid methods on Intel (R) Core (TM) i7-9750H architecture using C and obtain a 37.3% reduction in the implementation cycle count.