Optimized voronoi-based algorithms for parallel shortest vector computation

Abstract

This chapter addresses Voronoi cell-based algorithms, solving the Shortest Vector Problem, a fundamental challenge in lattice-based cryptanalysis. Several optimizations reduce the original algorithm's execution time. The algorithm suitability for parallel execution on both CPUs and GPUs is also shown. Optimizations are based on pruning, avoiding computations that will not improve the solution. The pruning criteria is related to the target vectors norm relative to the current best solution vector norm. Speedups up to 69× are observed. With a pre-process sorting step, which requires storing the norm ordered target vectors and therefore significantly more memory, speedup increases to 77×. On the parallel processing side, the optimized algorithm exhibits linear scalability on a CPU with up to 28 threads and keeps scaling, at a lower rate, with Simultaneous Multi-Threading up to 56 threads. The lack of support for efficient threads synchronization in GPUs precludes a scalable implementation of the pruning optimization. A parallel GPU version of the non-optimized algorithm is demonstrated to be competitive with the parallel non optimized CPU version, although the latter outperforms the former for 56 threads. GPUs are expected to outperform CPUs for higher lattice dimensions; this cannot be experimentally verified due to the limited memory available on current GPUs.