Paper 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Xeon Phivectornormlatticesieveshortest vector problem
Contact author(s)
dusan kostic @ epfl ch
History
2017-06-21: received
Short URL
https://ia.cr/2017/592
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/592,
      author = {Anja Becker and Dusan Kostic},
      title = {Speeding up lattice sieve with Xeon Phi coprocessor},
      howpublished = {Cryptology ePrint Archive, Paper 2017/592},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/592}},
      url = {https://eprint.iacr.org/2017/592}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.