International Association
for Cryptologic Research

Lattice-based cryptography is a promising candidate for providing cryptographic functions that remain secure in a post-quantum era. The security of lattice-based schemes relies on the hardness of lattice problems such as the problem of finding short vectors in integral lattices. In this work, we propose a new variant of the parallel Gauss sieve algorithm which can compute such short vectors. Our algorithm combines favorable properties of previous approaches: all vectors in the global list remain pairwise Gauss reduced (reducing the list size and runtime) while this list is split up between the participating nodes (lowering the memory requirements per node). To demonstrate the benefits of this variant, we present an optimized implementation of our parallel algorithm, using commonly available vector instruction set extensions. We conducted experiments with lattices of dimensions 80, 88, and 96, and the results show that the new approach outperforms the previous parallel Gauss sieve algorithms. The implementation will be made available, and we hope that it will serve as a basis for additional experiments.

Almost all recent implementations of lattice-based cryptographic schemes use ideal lattices, and it is known that sieving algorithms can benefit from their additional algebraic structure. Namely, the list size can be reduced by considering vectors along with all their rotations. We show that ideal lattices allow more optimizations, which enhance the performance of sieving algorithms even further. We use the fast Fourier transform (FFT) to speed up the computation of inner products between a vector and the rotations of another. On a conventional, academic computer cluster, our algorithm solved an SVP ideal lattice challenge in a negacyclic ideal lattice of dimension 128 in less than nine days using 1024 cores. This is more than twice as fast as the recent computation by Ishiguro et al. that solved the same challenge on a cluster with the same computer architecture, but without using large shared memory. This indicates that the FFT version can lead to a practical performance increase compared to a naive version using only rotations. Our results shed additional light on the security of schemes which rely on the hardness of computing short vectors in this special setting.