Cryptology ePrint Archive: Report 2017/592

Speeding up lattice sieve with Xeon Phi coprocessor

Anja Becker and Dusan Kostic

Abstract: Major substep in a lattice sieve algorithm which solves the Euclidean shortest vector problem (SVP) is the computation of sums and Euclidean norms of many vector pairs. Finding a solution to the SVP is the foundation of an attack against many lattice based crypto systems. We optimize the main subfunction of a sieve for the regular main processor and for the co-processor to speed up the algorithm in total. Furthermore, we show that the co-processor can provide a significant performance improvement for highly parallel tasks in the lattice sieve. Four-fold speed up achieved, compared to the CPU, indicates that co-processors are a viable choice for implementation of lattice sieve algorithms.

Category / Keywords: implementation / Xeon Phi, vector, norm, lattice, sieve, shortest vector problem

Date: received 19 Jun 2017

Contact author: dusan kostic at epfl ch

Available format(s): PDF | BibTeX Citation

Version: 20170621:142649 (All versions of this report)

Short URL: ia.cr/2017/592

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]