A Study on Some Approximations on the Average Number of the LLL Bases in Higher Dimensions

Abstract

The Lenstra-Lenstra-Lovász (LLL) algorithm, known as one of the main algorithms to decrypt the ciphertext encrypted by Lattice-based cryptography, outputs short basis vectors for n dimensional vectors represented by n × n matrix. One of the indicators that determine the quality of this LLL algorithm is the average number of the LLL bases, and there is a result related to the average number of the (δ, η)-LLL bases in dimension n in theoretical sense but the formula seems to be complicated and computing in high dimension takes a long time. In practical sense, we suggest some approximations which can be computed by just storing some constants and computing relatively simple exponential functions. To obtain the approximated results, we first express the existing results in a slightly simpler form, execute individual approximation for the part that takes a long time to calculate, and then combine the results. By finding the approximated value of the average number much faster, it helps to discuss the quality of the LLL algorithm for dimension n faster. Furthermore, in this process, we find a more precise upper bound of the average number of the (δ, η)-LLL bases in higher dimensions.