Lower Bound on the Overlattice-Based Sieve Algorithm

Lattice-based cryptography stands as one of the most pivotal candidates in post-quantum cryptography. To configure the parameters of lattice-based cryptographic schemes, a thorough comprehension of their concrete security is indispensable. Lattice sieving algorithms represent among the most critical tools for conducting concrete security analysis. Currently, the state-of-the-art BDGL-sieve (SODA 2016) achieves a time complexity of 20.292n+o(n), and Kirshanova and Laarhoven (CRYPTO 2021) have proven that the BDGL-sieve attains the lower bound under the technical paradigm of the Nearest Neighbor Search (NNS) problem. A natural question emerges: whether overlattice-based sieving algorithms (ANTS 2014) can outperform the BDGL-sieve within an alternative technical framework. This work provides an almost negative response to this question. Specifically, we propose a generalized overlattice tower model, which facilitates the proof of the lower bound for the overlattice-based method. Our findings indicate that the original Overlattice-sieve has already reached this lower bound. Consequently, the BDGL-sieve will maintain its status as the sieving algorithm with optimal time complexity, unless a revolutionary technical optimization is developed in the future.