Computational methods in discrete mathematics

About LLL reduction algorithms when solving the HNP problem and their comparative analysis

V. I. Yanov


Abstract: The paper examines a method for solving the hidden number problem (HNP) by reducing it to the closest vector problem. As part of this approach, careful testing of various implementations of the LLL and BKZ algorithms of lattice reduction is carried out, which are the main tools for solving the shortest vector problem. Particular attention is paid to comparing the experimental complexities of the two implemented algorithms: the fpLLL program, based on the 2009 Nguyen — Stehle's quadratic labor intensity method, and the algorithm from Ryan — Heninger. This benchmarking allows us to assess progress in improving the efficiency and speed of the task of finding hidden numbers. A key role in these experiments is played by careful tracking of the dependencies of the complexity of algorithms as the size of the lattice and the maximum element that make up this lattice grow. This allows us to identify the limitations of current approaches and suggest areas for further research and improvement of methods for solving the HNP.

Keywords: LLL-reduction, BKZ-reduction, HNP, fpLLL, Ryan — Heninger algorithm.

UDC: 511.482

DOI: 10.17223/2226308X/18/61