Sparse polynomial multiplication for lattice-based cryptography with small complexity

Akleylek S., Alkim E., Tok Z. Y.

JOURNAL OF SUPERCOMPUTING, cilt.72, sa.2, ss.438-450, 2016 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 72 Sayı: 2
  • Basım Tarihi: 2016
  • Doi Numarası: 10.1007/s11227-015-1570-1
  • Dergi Adı: JOURNAL OF SUPERCOMPUTING
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.438-450
  • Anahtar Kelimeler: Polynomial multiplication, Lattice-based cryptography, Sparse polynomial, Sliding window method, Software implementation
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

In this paper, we propose efficient modular polynomial multiplication methods with applications in lattice-based cryptography. We provide a sparse polynomial multiplication to be used in the quotient ring (Z/pZ)[x]/(x(n) + 1). Then, we modify this algorithm with sliding window method for sparse polynomial multiplication. Moreover, the proposed methods are independent of the choice of reduction polynomial. We also implement the proposed algorithms on the Core i5-3210M CPU platform and compare them with number theoretic transform multiplication. According to the experimental results, we speed up the multiplication operation in (Z/pZ)[x]/(x(n) + 1) at least 80% and improve the performance of the signature generation and verification process of GLP scheme significantly.