Paper 2017/592 Original: eprint.iacr.org/2017/592 ↗
Speeding up lattice sieve with Xeon Phi coprocessor
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.
- History
- 2017-06-21: last updated
- 2017-06-21: published
- Short URL
- https://ia.cr/2017/592
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2017/592}
}