On the efficiency of polynomial multiplication for lattice-based cryptography on GPUs using CUDA

Akleylek S., Dağdelen Ö., Tok Z. Y.

2nd International Conference on Cryptography and Information Security in the Balkans, BalkanCryptSec 2015, Koper, Slovenya, 3 - 04 Eylül 2015, cilt.9540, ss.155-168 identifier

  • Yayın Türü: Bildiri / Tam Metin Bildiri
  • Cilt numarası: 9540
  • Doi Numarası: 10.1007/978-3-319-29172-7_10
  • Basıldığı Şehir: Koper
  • Basıldığı Ülke: Slovenya
  • Sayfa Sayıları: ss.155-168
  • Anahtar Kelimeler: CUDA platform, CuFFT, Fast Fourier transform, GPU implementation, Lattice-based cryptography, NTT, Polynomial multiplication, Schönhage-Strassen
  • Ondokuz Mayıs Üniversitesi Adresli: Evet

Özet

Polynomial multiplication is the most time-consuming part of cryptographic schemes whose security is based on ideal lattices. Thus, any efficiency improvement on this building block has great impact on the practicability of lattice-based cryptography. In this work, we investigate several algorithms for polynomial multiplication on a graphical processing unit (GPU), and implement them in both serial and parallel way on the GPU using the compute unified device architecture (CUDA) platform. Moreover, we focus on the quotient ring (ℤ/pℤ) [x]/(xn + 1), where p is a prime number and n is a power of 2. We stress that this ring constitutes the most common setting in lattice-based cryptography for efficiency reasons. As an application we integrate the different implementations of polynomial multiplications into a lattice-based signature scheme proposed by Güneysu et al. (CHES 2012) and identify which algorithm is the preferable choice with respect to the ring of degree n.