On the combinatorial complexity of bounded sparse Learning With Errors (sLWE)

Abstract

Sparse Learning With Errors (sLWE), introduced at CRYPTO 2024 by Jain et al., is a recent variant of the Learning With Errors problem in which the traditionally dense public matrix is replaced by a sparse matrix whose rows contain only a small number of nonzero entries. This sparse structure substantially reduces storage requirements and computational costs, making sLWE a promising approach for improving the efficiency–security trade-off of lattice-based cryptography in the post-quantum setting. In their paper, the authors posed the open problem of understanding the security of sparse instances with small secrets. Motivated by this question, we study a bounded variant of sLWE in which both the secret and error vectors are restricted to the interval . We develop a combinatorial cryptanalytic framework based on subsystem extraction combined with a meet-in-the-middle strategy, enabling recovery of bounded secret vectors. Our analysis provides a detailed complexity evaluation across different sparsity and modulus regimes and yields concrete security estimates for the bounded setting. Our work does not claim any attack on the proposal of Jain et al.; instead, it provides a concrete analysis of sparse LWE with bounded secrets and errors, together with explicit complexity bounds showing reduced security margins in this setting. Our results indicate that security levels comparable to dimension-1024 LWE for the proposed parameter sets do not necessarily carry over to bounded sLWE, with the ternary case () providing a representative example. In this ternary setting, for modulus the secret can be recovered within practical complexity bounds, while for moduli and we observe a substantial reduction in the effective security margin. These findings provide a systematic cryptanalytic study of bounded sLWE and clarify how sparsity influences the security of LWE-type constructions.