Sparse polynomial multiplication for lattice-based cryptography with small complexity

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

JOURNAL OF SUPERCOMPUTING, vol.72, no.2, pp.438-450, 2016 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 72 Issue: 2
  • Publication Date: 2016
  • Doi Number: 10.1007/s11227-015-1570-1
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.438-450
  • Keywords: Polynomial multiplication, Lattice-based cryptography, Sparse polynomial, Sliding window method, Software implementation
  • Dokuz Eylül University Affiliated: No


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.