International Association
for Cryptologic Research

The security of lattice-based cryptosystems is determined by

the performance of practical implementations of, among others, algo-

rithms for the Shortest Vector Problem (SVP).

In this paper, we conduct a comprehensive, empirical comparison of two

SVP-solvers: ListSieve and GaussSieve. We also propose a practical par-

allel implementation of ListSieve, which achieves super-linear speedups

on multi-core CPUs, with efficiency levels as high as 183%. By compar-

ing our implementation with a parallel implementation of GaussSieve, we

show that ListSieve can, in fact, outperform GaussSieve for a large num-

ber of threads, thus answering a question that was still open to this day.