On the combinatorial complexity of bounded sparse Learning With Errors (sLWE)
Lade...
Autor:innen
Autor:in (Körperschaft)
Publikationsdatum
2026
Typ der Arbeit
Studiengang
Typ
01A - Beitrag in wissenschaftlicher Zeitschrift
Herausgeber:innen
Herausgeber:in (Körperschaft)
Betreuer:in
Übergeordnetes Werk
Designs Codes and Cryptography
Themenheft
DOI der Originalpublikation
Link
Zugehörige Forschungsdaten
Reihe / Serie
Reihennummer
Jahrgang / Band
94
Ausgabe / Nummer
Seiten / Dauer
206
Patentnummer
Verlag / Herausgebende Institution
Springer
Verlagsort / Veranstaltungsort
Auflage
Version
Programmiersprache
Abtretungsempfänger:in
Praxispartner:in/Auftraggeber:in
Zusammenfassung
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.
Schlagwörter
Fachgebiet (DDC)
Veranstaltung
Startdatum der Ausstellung
Enddatum der Ausstellung
Startdatum der Konferenz
Enddatum der Konferenz
Datum der letzten Prüfung
ISBN
ISSN
0925-1022
1573-7586
1573-7586
Sprache
Englisch
Während FHNW Zugehörigkeit erstellt
Ja
Zukunftsfelder FHNW
Publikationsstatus
Veröffentlicht
Begutachtung
peer-reviewed
Open Access-Status
Closed
Zitation
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