Solving Small LWE Instances with the Dropping Meet-in-the-Middle Algorithm

The Learning With Errors (LWE) problem serves as the security foundation for many post-quantum cryptographic schemes. Its various variants, including the sparse and small LWE problem, also play a key role in post-quantum cryptography. Accurately evaluating the computational complexity of solving LWE and its variants is important for understanding the security of related cryptographic schemes. In this paper, we propose an improved Dropping Meet-in-the-Middle (MitM) algorithm for LWE instances with sparse and small secrets. The core idea is to reduce the dimension of the MitM phase by pre-guessing τ components of the secret vector s, and to balance the additional guessing overhead against the reduction in the MitM phase, thereby achieving an overall optimization of computational cost. Experimental results show that our proposed method exhibits better performance compared with other attacks.