Paper 2021/973
A Multiplatform Parallel Approach for Lattice Sieving Algorithms
Michał Andrzejczak and Kris Gaj
Abstract
Lattice sieving is currently the leading class of algorithms for solving the shortest vector problem over lattices. The computational difficulty of this problem is the basis for constructing secure post-quantum public-key cryptosystems based on lattices. In this paper, we present a novel massively parallel approach for solving the shortest vector problem using lattice sieving and hardware acceleration. We combine previously reported algorithms with a proper caching strategy and develop hardware architecture. The main advantage of the proposed approach is eliminating the overhead of the data transfer between a CPU and a hardware accelerator. The authors believe that this is the first such architecture reported in the literature to date and predict to achieve up to 8 times higher throughput when compared to a multi-core high-performance CPU. Presented methods can be adapted for other sieving algorithms hard to implement in FPGAs due to the communication and memory bottleneck
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Published elsewhere. Minor revision. International Conference on Algorithms and Architectures for Parallel Processing - ICA3PP 2020
- DOI
- 10.1007/978-3-030-60245-1_45
- Keywords
- FPGAlattice sievinghardware accelerationmemory bottleneckcaching techniquespost-quantum cryptography
- Contact author(s)
-
michal andrzejczak @ wat edu pl
kgaj @ gmu edu - History
- 2021-07-22: received
- Short URL
- https://ia.cr/2021/973
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2021/973,
author = {Michał Andrzejczak and Kris Gaj},
title = {A Multiplatform Parallel Approach for Lattice Sieving Algorithms},
howpublished = {Cryptology ePrint Archive, Paper 2021/973},
year = {2021},
doi = {10.1007/978-3-030-60245-1_45},
note = {\url{https://eprint.iacr.org/2021/973}},
url = {https://eprint.iacr.org/2021/973}
}
