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

Loading...
Thumbnail Image
Author (Corporation)
Publication date
2026
Type of student thesis
Course of study
Type
01A - Journal article
Editors
Editor (Corporation)
Supervisor
Parent work
Designs Codes and Cryptography
Special issue
DOI of the original publication
Link
Related research data
Series
Series number
Volume
94
Issue / Number
Pages / Duration
206
Patent number
Publisher / Publishing institution
Springer
Place of publication / Event location
Edition
Version
Programming language
Assignee
Practice partner / Client
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.
Keywords
Project
Event
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
ISSN
0925-1022
1573-7586
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
peer-reviewed
Open access category
Closed
License
Citation
Kalam, A., Sarkar, S., & Meier, W. (2026). On the combinatorial complexity of bounded sparse Learning With Errors (sLWE). Designs Codes and Cryptography, 94, 206. https://doi.org/10.1007/s10623-026-01938-3