Paper 2024/2007
A Combinatorial Attack on Ternary Sparse Learning with Errors (sLWE)
Abstract
Sparse Learning With Errors (sLWE) is a novel problem introduced at Crypto 2024 by Jain et al., designed to enhance security in lattice-based cryptography against quantum attacks while maintaining computational efficiency. This paper presents the first third-party analysis of the ternary variant of sLWE, where both the secret and error vectors are constrained to ternary values. We introduce a combinatorial attack that employs a subsystem extraction technique followed by a Meet-in-the-Middle approach, effectively recovering the ternary secret vector. Our comprehensive analysis explores the attack's performance across various sparsity and modulus settings, revealing critical security limitations inherent in ternary sLWE.
Our analysis does not claim to present any attack on the proposal of Jain et al.; rather, it supports their assertion that sparse LWE is vulnerable for small secrets, particularly for ternary secrets and ternary errors. Notably, our findings indicate that the recommended parameters, which the developers claim provide security equivalent to LWE with a dimension of 1024, may not hold true for the ternary variant of sLWE.
Our research highlights that, particularly with a modulus of
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Sparse Learning With Errors (sLWE)Ternary sLWECombinatorial AttackPost-Quantum Cryptography
- Contact author(s)
-
abulkalam sunny @ gmail com
sarkar santanu bir1 @ gmail com
willimeier48 @ gmail com - History
- 2024-12-12: approved
- 2024-12-12: received
- See all versions
- Short URL
- https://ia.cr/2024/2007
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/2007, author = {Abul Kalam and Santanu Sarkar and Willi Meier}, title = {A Combinatorial Attack on Ternary Sparse Learning with Errors ({sLWE})}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/2007}, year = {2024}, url = {https://eprint.iacr.org/2024/2007} }