Noisy k-LIN over expanders

The noisy $k$-LIN over expanders conjecture conjectures that no efficient adversary can distinguish $(\mathbf{M},\mathbf{Ms}+\mathbf{e})$ from a uniformly random pair when $\mathbf{M}$ is a sparse expanding matrix over ${\mathbb{F}}_p$ — GHJS25, Conjecture 4.3. It is an ${\mathbb{F}}_p$ generalization of the Sparse LPN assumption; over ${\mathbb{F}}_2$, the two coincide. The name “$k$-LIN” also appears in bilinear map cryptography for the Decision $k$-Linear assumption — a group-theoretic hardness assumption in pairing groups unrelated to the sparse noise structure here.

Assumption

A matrix $\mathbf{M}\in {\mathbb{F}}_p^{m\times n}$ is $(\gamma ,d,N)$-expanding if each column has exactly $d$ nonzero entries drawn from ${\mathbb{F}}_p^{\ast }$, and for every set $S\subseteq [n]$ with $|S|\le N$, the neighborhood $\{i:M_{ij}\ne 0\text{ for some }j\in S\}$ has size at least $\gamma d|S|$. The GHJS25 conjecture instantiates this with $d=\Omega (\log n)$ and $N=2^{(\log n{)}^{\alpha }}$ for some $\alpha \in (0,1)$.

\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{nklin}}_{\calA}(\secpar)$}
\begin{algorithmic}
\State $\mathbf{M} \getsr \FF_p^{m \times n}$ with each column $(\gamma, d, N)$-expanding
\State $\mathbf{s} \getsr \FF_p^n$ ; $\mathbf{e} \getsr \mathrm{Ber}_p(\varepsilon)^m$
\Comment{Each $e_i = 0$ w.p. $1-\varepsilon$, uniform in $\FF_p^*$ w.p. $\varepsilon$}
\State $b \getsr \bits$
\State $\mathbf{v}_0 \gets \mathbf{M}\mathbf{s} + \mathbf{e}$ ; $\mathbf{v}_1 \getsr \FF_p^m$
\State $b' \gets \calA(1^\secpar, \mathbf{M}, \mathbf{v}_b)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}

Noisy $k$-LIN over $(\gamma ,d,N)$-expanders is hard if for all non-uniform polynomial-size $\mathcal{A}$,

$${\mathbf{Adv}}_{\mathcal{A}}^{\mathrm{nklin}}(\lambda ):=\left|2\mathrm{Pr}\left[{\mathbf{G}}_{\mathcal{A}}^{\mathrm{nklin}}(\lambda )=1\right]-1\right|$$

is negligible.

Known Results

• Noisy $k$-LIN over expanders is an ${\mathbb{F}}_p$ generalization of Sparse LPN; the two names refer to the same family of assumptions specialized to ${\mathbb{F}}_2$ vs. ${\mathbb{F}}_p$ — GHJS25, footnote 2
• Jointly with the planted clique conjecture against sub-exponential adversaries, noisy $k$-LIN over $(\gamma ,\Omega (\log n),2^{(\log n{)}^{\alpha }})$-expanders implies PKE secure against non-uniform polynomial-size circuits — GHJS25, Theorem 5.12
• A search variant of noisy $k$-LIN also suffices for the PKE construction under the joint assumption — GHJS25, Theorem 8.8

Variations

Noisy $k$-LIN over ${\mathbb{F}}_2$ (Sparse LPN)

Setting $p=2$ recovers Sparse LPN: the noise over ${\mathbb{F}}_2^{\ast }=\{1\}$ is simply a Bernoulli bit flip. Earlier works on pseudorandom correlation generators (PCGs) used “Sparse LPN” for this ${\mathbb{F}}_2$ case; GHJS25 adopts “noisy $k$-LIN” to emphasize the ${\mathbb{F}}_p$ generalization and the column-$k$-sparse structure of $\mathbf{M}$.

Search noisy $k$-LIN

The search variant asks to recover $\mathbf{s}$ from $(\mathbf{M},\mathbf{Ms}+\mathbf{e})$. The search-to-decision reduction for standard LPN does not immediately transfer to the expanding-matrix setting. GHJS25 Theorem 8.8 uses a search variant as an alternative assumption sufficient for PKE under the joint conjecture with planted clique.

Attacks

No efficient algorithms are known for the conjecture parameters. Over ${\mathbb{F}}_2$ (reducing to Sparse LPN), the best known attacks are variants of information-set decoding and BKW-style algorithms, whose complexity grows polynomially in $n$ only outside the conjecture’s parameter regime.