Halt Properties and Complexity Evaluations for Optimal DeepLLL Algorithm Families
This work addresses a foundational gap in lattice-based cryptography by formally proving halting properties for optimal parameters, which is incremental but crucial for algorithm reliability.
The paper tackles the problem of proving that four DeepLLL algorithm variants always halt with optimal parameter δ=1, where no polynomial bounds were previously known, and provides explicit upper bounds for loop counts in a unified way for all algorithms.
DeepLLL algorithm (Schnorr, 1994) is a famous variant of LLL lattice basis reduction algorithm, and PotLLL algorithm (Fontein et al., 2014) and $S^2$LLL algorithm (Yasuda and Yamaguchi, 2019) are recent polynomial-time variants of DeepLLL algorithm developed from cryptographic applications. However, the known polynomial bounds for computational complexity are shown only for parameter $δ< 1$; for "optimal" parameter $δ= 1$ which ensures the best output quality, no polynomial bounds are known, and except for LLL algorithm, it is even not formally proved that the algorithm always halts within finitely many steps. In this paper, we prove that these four algorithms always halt also with optimal parameter $δ= 1$, and furthermore give explicit upper bounds for the numbers of loops executed during the algorithms. Unlike the known bound (Akhavi, 2003) applicable to LLL algorithm only, our upper bounds are deduced in a unified way for all of the four algorithms.