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 $2^{64}$, the secret key can be recovered in a practical timeframe, supporting the developers' claim of vulnerability in this case. Additionally, for configurations with moduli of $2^{32}$ and $2^{16}$, we observe a significant reduction in the security margin. This suggests that the actual security level may be significantly weaker than intended. Overall, our work contributes crucial insights into the cryptographic robustness of ternary sLWE, emphasizing the need for further strengthening to protect against potential attacks and setting the stage for future research in this area.