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 (Journal Indexed in SCI) identifier identifier

  • Publication Type: Article / Article
  • Volume: 72 Issue: 2
  • Publication Date: 2016
  • Doi Number: 10.1007/s11227-015-1570-1
  • Title of Journal : JOURNAL OF SUPERCOMPUTING
  • Page Numbers: pp.438-450
  • Keywords: Polynomial multiplication, Lattice-based cryptography, Sparse polynomial, Sliding window method, Software implementation

Abstract

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.