TU Darmstadt / ULB / TUbiblio

On the Efficiency of Polynomial Multiplication for Lattice-Based Cryptography on GPUs Using CUDA

Akleylek, Sedat and Dagdelen, Özgür and Tok, Zaliha Yüce :
On the Efficiency of Polynomial Multiplication for Lattice-Based Cryptography on GPUs Using CUDA.
In: LNCS , 9540 . Springer
[Conference or Workshop Item] , (2016)

Abstract

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 (Z/pZ)[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.

Item Type: Conference or Workshop Item
Erschienen: 2016
Creators: Akleylek, Sedat and Dagdelen, Özgür and Tok, Zaliha Yüce
Title: On the Efficiency of Polynomial Multiplication for Lattice-Based Cryptography on GPUs Using CUDA
Language: English
Abstract:

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 (Z/pZ)[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.

Title of Book: Cryptography and Information Security in the Balkans
Series Name: LNCS
Volume: 9540
Publisher: Springer
Uncontrolled Keywords: Primitives; P1; Lattice-based cryptography; GPU implementation; CUDA platform; Polynomial multiplication; Fast Fourier transform; cuFFT; NTT; Schönhage-Strassen
Divisions: Department of Computer Science
Department of Computer Science > Theoretical Computer Science - Cryptography and Computer Algebra
DFG-Collaborative Research Centres (incl. Transregio)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres
Profile Areas
Profile Areas > Cybersecurity (CYSEC)
DFG-Collaborative Research Centres (incl. Transregio) > Collaborative Research Centres > CRC 1119: CROSSING – Cryptography-Based Security Solutions: Enabling Trust in New and Next Generation Computing Environments
Event Location: Koper, Slovenia
Date Deposited: 06 Sep 2018 11:16
Export:

Optionen (nur für Redakteure)

View Item View Item