Shortest Lattice Vector Enumeration on Graphics Cards?

Abstract. In this paper we make a first feasibility analysis for imple-menting lattice reduction algorithms on GPU using CUDA, a program-ming framework for NVIDIA graphics cards. The enumeration phase of the BKZ lattice reduction algorithm is chosen as a good candidate for massive parallelization on GPU. Given the nature of the problem we gain large speedups compared to previous CPU implementations. Our imple-mentation saves more than 50 % of the time in high lattice dimensions. Among other impacts, this result influences the security of lattice based cryptosystems