Paper 2026/630

Asymptotic Analysis of Ternary Sparse LWE

Nathan Cho, Korea University

Jiseung Kim, Jeonbuk National University

Changmin Lee, Korea University

Abstract

We present an asymptotic analysis of the ternary variant of Sparse Learning with Errors (spLWE), a structured LWE variant proposed by Jain--Lin--Saha (CRYPTO'24) in which each equation involves only $k \ll n$ of the $n$ secret coordinates, enabling significantly more efficient computation than dense LWE. Unlike standard LWE, the small-secret regime of spLWE is not automatically reducible to its large-secret counterpart, leaving asymptotic hardness unclear, particularly when $k$ is very small. We develop a two-pronged attack framework that depends explicitly on the sparsity parameter $k$. In the geometric regime $q > 3^k$, each sparse row reduces to a short-vector problem in a $k$-dimensional lattice, yielding complexity $2^{0.292k}$ via a sieving algorithm. In the statistical regime $q \leq 3^k$, we propose a greedy coordinate-recovery attack with running time $O(m \cdot k \cdot 3^k)$, where $m$ is the number of samples. Heuristically, under mild assumptions, full recovery holds with high probability once the sample size is large enough; the resulting complexity is exponential only in $k$ and otherwise mild (up to polylogarithmic factors), i.e., polynomial in $n$, which makes very small $k$ vulnerable even at large dimensions. Experiments on toy instances confirm the predicted sharp transition. Complexity comparisons with prior works indicate lower complexity on a few of their parameter sets, while identifying regimes where our method is not applicable.

@misc{cryptoeprint:2026/630,
      author = {Byoungchan Chi and Nathan Cho and Jiseung Kim and Changmin Lee},
      title = {Asymptotic Analysis of Ternary Sparse {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/630},
      year = {2026},
      url = {https://eprint.iacr.org/2026/630}
}