Paper 2021/1136

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

Michael Burger, Christian Bischof, and Juliane Krämer


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.

Available format(s)
Publication info
Published elsewhere. HPCS 2019
Lattice-based cryptographyExtreme pruningOpenMPParallel lattice enumerationParallel simulated annealingHeuristic optimization
Contact author(s)
juliane @ qpc tu-darmstadt de
michael burger @ sc tu-darmstadt de
2021-09-07: received
Short URL
Creative Commons Attribution


      author = {Michael Burger and Christian Bischof and Juliane Krämer},
      title = {A new Parallelization for p3Enum and Parallelized Generation of Optimized Pruning Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1136},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.