Paper 2021/1136

A new Parallelization for p3Enum and Parallelized Generation of Optimized Pruning Functions

Michael Burger, Christian Bischof, and Juliane Krämer

Abstract

Since quantum computers will be able to break all public-key encryption schemes employed today efficiently, quantum-safe cryptographic alternatives are required. One group of candidates are lattice-based schemes since they are efficient and versatile. To make them practical, their security level must be assessed on classical HPC systems in order to determine efficient but secure parameterization. In this paper, we propose a novel parallelization strategy for the open source framework p3Enum which is designed to solve the important lattice problem of finding the shortest non-zero vector in a lattice (SVP). We also present the p3Enum extreme pruning function generator (p3Enum-epfg) which generates optimized extreme pruning functions for p3Enum’s pruned lattice enumeration by employing a parallelized simulated annealing approach. We demonstrate the quality of the pruning functions delivered. Combining the new parallelization with optimized pruning functions speeds up p3Enum by a factor up to 3 compared to the previous version. Additionally, we compare the required runtime to solve the SVPs with state-of-the art tools and, for the first time, also visualize the statistical effects in the runtime of the algorithms under consideration. This allows a considerably better understanding of the behavior of the implementations than previous average-value considerations and demonstrates the relative stability of p3Enum’s parallel runtimes which improve reproducibility and predictability. All these advancements make it the fastest SVP solver for lattice dimensions 66 to 92 and a suitable building block as SVP-oracle in lattice basis reduction.