Technical Summary: Hardness Amplification for (Sparse) LPN

Problem Statement

The paper addresses the Learning Parity with Noise (LPN) problem and its Sparse-LPN variant. In the standard search version of LPN ($LPN_{\eta, n, m}$), the goal is to recover a secret vector $s \in \mathbb{F}_2^n$ given $m$ noisy linear samples $(A, b)$, where $b = As + e$. Here, $A$ is a uniform matrix, and the noise vector $e$ consists of independent Bernoulli variables with parameter $\eta$.

The Sparse-LPN variant restricts the rows of $A$ to have a specific Hamming weight $\sigma$ (often $\sigma = O(1)$). While LPN serves as a foundational assumption for various cryptographic primitives (e.g., authentication, public-key encryption, pseudorandom generators), establishing its average-case hardness remains a challenge.

The central question addressed is whether one can prove an "almost" worst-case-to-average-case reduction. Specifically, can hardness on a small fraction $\delta$ of random instances be amplified to hardness on almost all instances (and thus average-case hardness) under standard parameter transformations? Existing worst-case-to-average-case reductions for LPN rely on code smoothing, which currently only works for extremely low error rates (far from cryptographic regimes) or requires parameters that make the problem algorithmically easy. For Sparse-LPN, no such reductions exist in cryptographic regimes.

Methodology

The authors adopt a hardness self-amplification approach, building on the direct-product framework introduced by Hirahara and Shimizu [HS23]. Instead of reducing from a worst-case instance, they work directly with the average-case distribution to show that solving a small fraction of instances implies solving almost all instances.

The core technical strategy involves three main steps:

1. Direct-Product Embedding:
   The authors construct an explicit embedding that maps $k$ independent LPN instances of dimension $n/k$ into a single larger LPN instance of dimension $n$.

   • Given $k$ instances $(A_i, b_i = A_i s_i + e_i)$, they form a concatenated matrix $A = [A_1 | \dots | A_k]$ and a summed response vector $b = \sum b_i$.
   • The resulting system is $b = As + e'$, where $s = (s_1, \dots, s_k)$.
   • Crucially, the noise distribution transforms predictably. For binary LPN, if the base noise is $\eta$, the new noise rate becomes $\eta' = \frac{1 - (1-2\eta)^k}{2}$. For $q$-ary LPN, it becomes $\eta' = 1 - (1-\eta)^k$.
   • This allows a solver for the single large instance (with higher noise) to be converted into a solver for the $k$ independent small instances (with lower noise) with the same success probability.

2. Amplification via Sampling Analysis:
   Using the framework of [HS23], the authors analyze the standard direct-product reduction as a sampler. They show that if an algorithm solves the product distribution (the $k$-fold instance) with probability $\epsilon$, it can be transformed into an algorithm that solves the base distribution with probability $1-\delta$ on a $1-\delta$ fraction of inputs. This requires $k = \Theta(\frac{1}{\delta} \log \frac{1}{\epsilon})$.

3. Handling Sparsity via Approximate-Sparse Variants:
   Standard Sparse-LPN requires rows to have exactly weight $\sigma$. However, the concatenation of sparse matrices does not preserve exact sparsity. To overcome this, the authors introduce an approximate-sparse variant ($LPN^{\approx \sigma}$), where each entry of $A$ is 1 independently with probability $\sigma/n$ (resulting in an expected row weight of $\sigma$).

   • This distribution is closed under the concatenation embedding.
   • They prove self-amplification for this approximate-sparse variant.
   • Finally, they provide a filtering reduction from the approximate-sparse variant to the exact-sparse variant ($LPN^{=\sigma}$). By discarding rows that do not have exactly weight $\sigma$, they recover a valid exact-sparse instance, incurring only a controlled blowup in the number of samples.

Key Contributions and Results

1. Instance-Fraction Amplification for LPN:
   The paper proves that for any $\epsilon, \delta > 0$, an algorithm solving $LPN_{\eta, n, m}$ with success probability $\epsilon$ can be transformed into an algorithm that succeeds with probability $1-\delta$ on a $1-\delta$ fraction of instances of a related distribution with scaled parameters. This holds for both binary and $q$-ary fields.

2. Amplification for Sparse-LPN:
   The authors extend these results to Sparse-LPN. They establish hardness self-amplification for the approximate-sparse variant and reduce it to the standard exact-sparse variant. This is the first result of its kind for Sparse-LPN in cryptographic parameter regimes, as previous smoothing-based approaches failed to preserve sparsity or required non-cryptographic parameters.

3. Parameter Regimes:
   The amplification holds in standard cryptographic noise regimes, including constant noise and noise rates as low as $\eta = 1/n^\alpha$. The results do not force parameters into the "easy" regime (e.g., $\eta \approx (\log n)/n$) where Gaussian elimination would succeed.

4. Verification and Decodability:
   The proofs rely on the fact that for appropriate parameters, LPN instances are uniquely decodable with high probability. The authors provide rigorous bounds (using Chernoff bounds and Gilbert-Varshamov type arguments) showing that the noise vector is small enough and the code distance large enough to ensure unique recovery of the secret.

Significance and Claims

The paper claims to strengthen the foundations for assuming the average-case hardness of LPN and its sparse variants. By demonstrating that hardness on a small fraction of instances implies hardness on almost all instances, the work provides a "next best" alternative to a full worst-case-to-average-case reduction.

• For LPN: It establishes that the average-case hardness of LPN is robust; if an adversary can break the problem on a non-negligible fraction of inputs, they can be amplified to break it on almost all inputs.
• For Sparse-LPN: It resolves a significant gap in the literature. Unlike LWE, Sparse-LPN lacked worst-case-to-average-case reductions. This work provides the first self-amplification results for Sparse-LPN in cryptographic regimes, validating its use in constructions like indistinguishability obfuscation and pseudorandom generators.

The authors explicitly note that their approach avoids the bottlenecks of "leftover-hash" style smoothing, which fails for sparse instances due to entropy constraints and sparsity destruction. Instead, their direct-product embedding preserves the structure of the problem while amplifying hardness. They leave open the question of achieving a true worst-case-to-average-case reduction with comparable parameters, positioning their result as a significant step toward that goal.