Cryptology ePrint Archive: Report 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

Category / Keywords: implementation / FPGA, lattice sieving, hardware acceleration, memory bottleneck, caching techniques, post-quantum cryptography

Original Publication (with minor differences): International Conference on Algorithms and Architectures for Parallel Processing - ICA3PP 2020

Date: received 20 Jul 2021

Contact author: michal andrzejczak at wat edu pl, kgaj at gmu edu

Available format(s): PDF | BibTeX Citation

Version: 20210722:092048 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]