The analysis of Hermite factor of BKZ algorithm on small lattices

Abstract

Lattice cryptography is one of the promising directions in modern cryptography research. Digital signatures and key encapsulation mechanisms on lattices have already been used in practice. In the future, such quantum-resistant transformations on lattices replace all standards that are not resistant to attacks on quantum computers. This makes the analysis of their security extremely relevant. Analysis of the security of cryptographic transformations on lattices is often reduced to the estimation of the minimum block size in the lattice reduction algorithm. For the expansion of small vectors, a reduction algorithm can be obtained for a given block size, the GSA model is often used, which uses the so-called Hermitian factor to predict the size of the vectors that the lattice reduction algorithm can obtain given the parameters. Asymptotic formulas have been developed to evaluate it in practice, but the question of their accuracy on cryptographic lattices has not been fully investigated. The work obtained estimates of the accuracy of the existing asymptotic estimates of the Hermite factor for lattices of sizes 120, 145, 170 for the classical BKZ algorithm. Research was conducted using the fpylll library. It was shown that the existing estimators are equivalent from a practical point of view and have a sufficiently small root mean square deviation from the true values. A formula was obtained that binds the root-mean-square error of approximation of the Hermit factor to the cryptographic parameters of lattices. The obtained results are useful for refining the security assessments of existing cryptographic transformations.