p3Enum: A Parallel, Parameterizable Open-Source Framework for Enumeration with Extreme Pruning

p3Enum: A Parallel, Parameterizable Open-Source Framework for Enumeration with Extreme Pruning

Burger, Michael, p3Enum: A Parallel,  Parameterizable Open-Source Framework for Enumeration with Extreme Pruning Figure1 Burger, Michael, p3Enum: A Parallel, Parameterizable Open-Source Framework for Enumeration with Extreme Pruning Figure1

Figure 1: Runtime comparison of the recent p3Enum-version (pEnumOpt) with its predecessor and with the state-of-the-art fplll-library based on pruned enumeration and SubSieve as a sieving based solution.

Michael Burger
Burger, Michael, p3Enum: A Parallel,  Parameterizable Open-Source Framework for Enumeration with Extreme Pruning Figure2 Burger, Michael, p3Enum: A Parallel, Parameterizable Open-Source Framework for Enumeration with Extreme Pruning Figure2

Figure 2: Speedup when increasing the number of threads for 88-dimensional lattices. Based on 360 measurement points. Red line connects the averages.

Michael Burger

Einleitung

In our project, we investigate the hardness of various instances of the shortest vector problem (SVP) which are the bases of novel schemes for quantum-safe cryptography. To that end, we employ our open-source software p3Enum which was developed, tested and optimized within this project. Our package is based on a parallelized implementation of the enumeration algorithm with extreme pruning which searches the coefficients of the shortest vector in a heuristically pruned tree. The SVP is known to be NP-hard and the required runtime to solve it grows exponentially with the dimension of the lattice in which the search is processed. Additionally, the random nature of the algorithm results in highly varying runtimes for different runs to solvethe same problem instance, requiring many repetitions in order to understand its behavior in detail. Investigating problems of dimensions higher than 100 may require many hours of runtime although our software is efficiently parallelized.

Methoden

The p3Enum-software is written in C++-11 and parallelized with OpenMP. It automatically increases the workload during the search in a pruned search-tree by relaxing the pruning strategy, meaning that more nodes are left in the tree. If appropriately parametrized, a parallel run of our enumeration takes about the same runtime as the standard serial enumeration but visits much more nodes in the tree and thus increases the success probability. Synchronization between threads is minimized by new thread-safe and shared data structures. The single-core performance was also optimized based on profiled runs.

Ergebnisse

We performed a detailed performance comparison with other state-of-the-art frameworks and demonstrated that p3Enum is the fastest SVP solver for dimensions ≤ 92 due to its parallelization. The parallel efficiency is still near 0.7 when employing 24 cores on the dual core Haswell systems of the HHLR, although parts of the parallel solution process are memory bound. Additionally, we highlighted that p3Enum provides relatively stable runtimes for the solution of the problems, in contrast to the other software packages considered.

Diskussion

The fast runtimes combined with their stability and reproducibility make p3Enum a good candidate as SVP oracle in lattice reduction frameworks, since during the basis reduction many SVP instances in smaller dimensions have to be solved. Additionally, the data gathered allows a better understanding of the runtime behavior of enumeration with extreme pruning and will help us to develop models to predict the runtime of higher lattice dimension which are needed in order to set appropriate parameters for quantum-safe cryptography.

Last Update

  • Last Update: