Katholieke Universiteit Leuven
In this paper the authors make a first feasibility analysis for implementing lattice reduction algorithms on GPU using CUDA, a programming 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 they gain large speedups compared to previous CPU implementations. Their implementation saves more than 50% of the time in high lattice dimensions. Among other impacts, this result influences the security of lattice based cryptosystems.