Efficient Parallel Implementations of Enumeration Algorithms for SVP and BKZ Computations

02.012.2014, 10:30 – 11:30

2014/12/02 10:30-11:30

Speaker: Fábio Correia | Location: Mornewegstraße 32 (S4|14), Room 3.2.01, Darmstadt

Organizer: CROSSING, Prof. Bischof


Lattice-based cryptography has been a hot topic in the past decade, since it is believed that lattice-based cryptosystems are immune against attacks operated by quantum computers. The security of this type of cryptograpphy is based on the hardness of algorithms that solve the shortest vector problem (SVP). Algorithms that solve the SVP are called SVP-solvers.

A wide range of SVP-solvers were proposed in the past. This presentation will focus on enumeration-based SVP-solvers. We implemented a parallel version of the enumeration algorithm ENUM on a shared memory system based on a dual (8+8)-core device. This implementation led to linear speedups for up to 8 threads and almost linear speedups for 16 threads. Currently, the fastest algorithm in practice is the enumeration with extreme pruning, which consists in applying the extreme pruning technique to enumeration-based solvers. We implemented a parallel version of this algorithm with MPI, which achieved speedups of up to 12.96x for 16 processes.

Specific algorithms can be used to increase the performance of SVP-solvers, called lattice basis reduction algorithms. One of the most used algorithms, in practice, is BKZ, which uses internally LLL, another lattice basis reduction algorithm, and ENUM, an enumeration-based SVP-solver. Two parallel implementations of BKZ were tested. The first changes the workflow of the algorithm, while the other follows the original workflow of the algorithm, using a parallel implementation of ENUM.