Parallelizing the Hybrid Lattice-Reduction and Meet-in-the-Middle Attack
Thomas Wunderer, Michael Burger, Giang Nam Nguyen · 2018
The hybrid lattice reduction and meet-in-the-middle attack (the hybrid attack) is currently one of the most practical attacks on lattice-based cryptosystems with small and/or sparse secrets. We show how to parallelize the hybrid attack, determine the theoretical speedup of the parallel over the serial attack, and demonstrate how this influences security estimates of lattice-based cryptosystems. Our parallel hybrid attack increases the success probability of the attack and reduces the cost of the guessing phase. A hybrid parallelization approach employing MPI and OpenMP is applied in our C++ implementation. The resulting software is highly configurable to the underlying binary LWE instance enabling to make full use of the hardware at hand. Our implementation can considerably increase the success probability of the hybrid attack by running multiple, randomized instances in parallel with minimized MPI communication. The guessing phase of the attack is shared-memory parallelized and we achieve an efficiency of about 90% on our system providing 24 physical cores per node. This enables our implementation to outperform a reference implementation in the SageMath package within the guessing phase by a factor higher than 600.