TY - JOUR
AU - Song, Kyunghwan
AU - Seo, Yun Am
PY - 2024/06/16
Y2 - 2024/08/12
TI - A Study on the Average Number of LLL-based Using Statistical Learning
JF - International Journal on Advanced Science, Engineering and Information Technology
JA - Int. J. Adv. Sci. Eng. Inf. Technol.
VL - 14
IS - 3
SE - Articles
DO - 10.18517/ijaseit.14.3.19890
UR - https://ijaseit.insightsociety.org/index.php/ijaseit/article/view/19890
SP - 906-911
AB - <p>Lattice-based Cryptography is known as one of the key technologies in modern cryptography. This encryption scheme has the basis vectors from the lattice as the public key and a short-length vector in the lattice consisting of an integer combination of the basis vectors as the secret key. To break this encryption, we need to solve the Shortest Vector Problem (SVP), known as NP-hard. Therefore, instead of finding the shortest vector, LLL algorithm is often used to find a vector of sufficiently short length to break the encryption. The LLL algorithm is a well-known method for breaking this encryption, but there is still no clear answer to the question of how many times the LLL algorithm needs to be used to obtain the desired level of secret key, the average number of the (, )-LLL bases in dimension n is a tool to measure the probability that the LLL algorithm solves the SVP. We can expect that this number indicates how many times the appropriate algorithm should run. There is a formula for this, but it contains some functions that take a long time to compute. We apply linear regression to the formula of the average number of the (, )-LLL bases in dimension n, and therefore we obtain some formulas to approximate the average number of the (, )-LLL is based on dimension n, which contains simple functions. When the dimensions are high, our model is much better regarding the computation time.</p>
ER -