Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs

Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar · 2026

Read Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs by Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-27190.txt.

Introduction

Agrawal and co-authors give a spectral attack on sparse learning-with-errors style problems over general rings. The task is telling random right-hand sides from planted noisy sparse equations. Their algorithm runs in a stated time bound for a range of sparsity parameters. It fails only with tiny probability when enough samples are available. The method generalizes the Kikuchi approach from bits to rings of any finite size. Earlier hardness claims for sparse LWE are shown to be tight.

Catalog record

CREATORShashwat Agrawal, Amitabha Bagchi, Rajendra Kumar
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE133863
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.27190

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Attacks on Sparse LWE and Sparse LPN with new Sample-Time tradeoffs Shashwat Agrawal, Amitabha Bagchi, Rajendra Kumar Abstract This paper extends the Kikuchi method to give algorithms for decisional k k -sparse Learning With Errors (LWE) and k k -sparse Learning Parity with Noise (LPN) problems for higher moduli q q . We create a Kikuchi graph for a sparse LWE/LPN instance and use it to give two attacks for these problems. The first attack decides by computing the spectral norm of the adjacency matrix of the Kikuchi graph, which is a generalization of the attack for q = 2 q=2 given by Wein et. al. (Journal of the ACM 2019). The second approach computes non-trivial closed walks of the graph, and then decides by computing a certain polynomial of edge labels in the walks. This is a generalization of the attack for q = 2 q=2 given by Gupta et. al. (SODA 2026). Both the attacks yield new tradeoffs between sample complexity and time complexity of sparse LWE/LPN. 1 Introduction The Learning With Errors (LWE) problem, introduced by Regev [ Reg05 ] , and its close cousin, the Learning Parity with Noise (LPN) problem [ Ale03 ] , form central hardness assumptions in modern cryptography. In LWE, samples from the distribution \mathcal{A}_{s,\chi} on \mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q} are generated by selecting \bm{a}\in\mathbb{Z}_{q}^{n} uniformly at random, an error e\in\mathbb{Z}_{q} from a distribution \chi (typically a discrete Gaussian with width r<q ), and computing (\bm{a},\langle\bm{a},\bm{s}\rangle+e) modulo q ; the decision version requires distinguishing these from uniform samples on \mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q} . LPN, most commonly studied over \mathbb{Z}_{2} with Bernoulli noise or more generally over modulus q with small hamming weight error, shares similar structure. Most lattice-based cryptosystems rely on LWE’s conjectured intractability against classical and quantum algorithms [ Reg05 , Pei09 , Gen09 , BV14 , Pei16 ] , while LPN’s hardness rests on decades of cryptanalysis [ Gol00 , CM01 , Fei02 , MST03 , AOW15 , AL16 , KMOW17 ] , offering competitive efficiency despite fewer constructions [ Pie12 , ADINZ17 ] . Variants of these problems are considered to balance security with efficiency of cryptographic primitives. Different choices of modulus, noise distribution, or structural constraints (such as sparsity) can lead to primitives with faster key generation, smaller ciphertexts, or reduced computational overhead, while still relying on problems which are believed to have same hardness [ LPR13 , ABW10 ] . In this work, we focus on LWE and LPN with sparsity constraints. A sparse version can be considered where the coefficient vectors \bm{a}\in\mathbb{Z}_{q}^{n} have only k non-zero entries for a parameter k<n . The motivation for this sparsity is that the samples can be computed and stored with a roughly O(n/k) factor improvement in efficiency. Hardness of sparse LPN over \mathbb{Z}_{2} and variants have been studied for as long as forty years in average-case complexity and have intimate connections to constraint satisfaction problems [ Hs84 , Gol11 , AOW15a , AL16a , KMOW17a ] . Sparse variants of LWE/LPN over large moduli q (where q is at least polynomial in the security parameter) are useful for designing efficient advanced cryptographic primitives, including FHE but remain underexplored. We summarize the current known attacks for sparse variants below. The task in analyzing the hardness of sparse LPN over \mathbb{Z}_{2} (and in fact, sparse LWE in general) is to determine the computational complexity as a function of m , i.e. the number of samples (\bm{a},b) . For m\leq n , the random and the planted noisy instances are statistically indistinguishable. Raghavendra, Rao and Schramm [ RRS17 ] showed that sparse LPN over \mathbb{Z}_{2} can be solved in n^{O(l)} time when m is a quantity of the form l\left(\frac{n}{l}\right)^{k/2}\log^{c(k)}(n) using a degree l “Sum of squares” method for l\geq k/2 . An improved (and the best known) bound of the form l\left(\frac{n}{l}\right)^{k/2}\log{n} for m with the same time complexity can be obtained using the “Kikuchi method” by Wein, Alaoui, and Moore [ WEAM19 ] (independently by Hastings [ Has20 ] ). 1 1 1 The Kikuchi method is inspired from Kikuchi free energy, a marginal approximation to Gibbs free energy [ Kik51 ] Schmidhuber, O’Donnell, Kothari, and Babbush [ SOKB25 ] gave a quantum algorithm that achieves a quartic speedup in time (i.e. n^{l/4}\cdotp\text{poly}(n) ) over the Kikuchi method for certain choices of the sample complexity m , while using exponentially less space. More recently, Gupta, He, O’Donnell, and Singer [ GHOS26 ] used the Kikuchi graph defined by [ WEAM19 ] and gave a new classical algorithm with a nearly quadratic speedup over the Kikuchi Method for the same sample complexity. Despite the presence of numerous other variants of LWE, sparse LWE was not studied until a recent work by Jain, Lin, and Saha [ JLS24 ] . Assuming hardness of sparse LWE, the authors construct secret key Linearly Homomorphic Encryption (LHE) schemes with slightly super-constant/constant overheads, and secret key homomorphic encryption for arbitrary constant-degree polynomials with slightly super-constant/constant overheads. They also perform some cryptanalysis on sparse LWE by suggesting two attacks for sparse LWE, namely the sparse vector in kernel attack and the dense minor attack. On analyzing the feasibility of these attacks for k\geq\Omega(\log n) and m=\text{poly}(n) , it turns out that these attacks will take exponential time in n with high probability. Hence, the authors conjecture that sparse LWE with sparsity k\geq\Omega(\log n) and polynomially many samples m=\text{poly}(n) is as hard as the standard LWE with dimension n^{\prime}=\Theta(n) and polynomially many samples. Our Contributions. This work is towards a more fine-grained analysis of the complexity of sparse LWE and sparse LPN over higher moduli. In particular, we obtain tradeoffs between the sample complexity m and time complexity for sparse LWE and sparse LPN over higher moduli q . Theorem 1.1 . (Informal) For dimension n , number of samples m\geq\left(\frac{n}{l}\right)^{k} , modulus q , width parameter r<q , and a tradeoff parameter k/2\leq l\leq n : • (Theorem 5.20 ) There exists an algorithm that solves the decisional k -sparse LWE in \widetilde{O}\left(\binom{n}{l}q^{l}\right) time. • (Theorem 6.15 ) If q is prime, q\gg r(l\log n)^{3/2} , there exists an algorithm that solves the decisional k -sparse LWE in \widetilde{O}\left(\sqrt{\binom{n}{l}q^{l}}(n/l)^{k}\right) time. Theorem 1.2 . (Informal) For dimension n , number of samples m\geq\left(\frac{n}{l}\right)^{k} , modulus q , probability mass for non-zero error \mu=\frac{q-1}{q}-\frac{1}{\text{poly}(n)} , and a tradeoff parameter k/2\leq l\leq n : • (Theorem 5.21 ) There exists an algorithm that solves the decisional k -sparse LPN in \widetilde{O}\left(\binom{n}{l}q^{l}\right) time. • (Theorem 6.20 ) If q is prime, there exists an algorithm that solves the decisional k -sparse LPN in \widetilde{O}\left(\left(\binom{n}{l}q^{l}\right)^{1/2+\varepsilon}(n/l)^{k}\right) time for an arbitrarily small constant \varepsilon . As can be seen, the parameter l in the above theorems trades sample complexity for time. As an interesting case, if either k=O(\log n/\log\log n) or we are allowed m=n^{\Omega(\log\log n)} samples, we can choose l appropriately so that the time complexity is \exp({\delta n}) for arbitrarily small \delta>0 . Thus, assuming standard LWE does not have an arbitrary small exponential time, our result also establishes the tightness of the above conjecture on the hardness of sparse LWE by [ JLS24 ] . Our methodology is to define a {k}\mbox{-}\text{LIN}_{q} instance as a generalization

Read the complete text