Worst-case to average-case hardness reduction for the Learning Parity with Noise problem

Worst-case to average-case hardness reduction for the Learning Parity with Noise problem

Definitions and mathematical statement

For a secret $s\in{\mathbb{F}}_2^n$ and a fixed noise rate $0<\eta<1/2$, a Learning Parity with Noise sample is \[ (a,b),\qquad a\sim\operatorname{Unif}({\mathbb{F}}_2^n),\quad b=\langle a,s\rangle+e\pmod2,\quad e\sim\operatorname{Bernoulli}(\eta), \] with independent samples and errors. Search LPN recovers $s$ with significant probability from polynomially many samples; decision LPN distinguishes these samples from uniform pairs. The task asks for a worst-case-to-average-case hardness reduction from a worst-case decoding problem to standard constant-noise LPN. A decoding input typically specifies a binary code and a received word, with a distance promise, and asks for a nearby codeword. The catalogue does not select the source promise, approximation factor, reduction type, or search/decision version. These choices must be fixed in any claimed reduction; a low-noise result alone does not provide the stated constant-noise conclusion.

Formulation and concept references: [S1].

Short English statement

Can hardness of decoding arbitrary worst-case code instances be transferred rigorously to learning random noisy parities with a fixed positive noise rate?

Research attempt

Status: UNRESOLVED. This entry has an underspecified source decoding problem, so no single reduction theorem is silently chosen as its answer. We prove exact randomization of the secret, an information-theoretic recovery bound, a search-to-distinguishing implication, and a rigidity statement explaining why naive random linear mixing destroys the required noise law. These do not give a reduction from arbitrary hard code instances to standard constant-noise LPN.

Source audit and a noise-rate qualification.

The September 2026 revision of [S1], consulted on 27 September 2026, describes a win-win reduction: for a specified matrix, the derived algorithms either decode its code from random noise or distinguish noisy words in its dual from uniform. Its low-noise hardness conclusion assumes simultaneous worst-case hardness of those tasks. That is more specific than hardness of an unspecified arbitrary-received-word decoding problem. The archive abstract and parameter description were checked; the entire paper's proof is not independently certified here.

There is a useful qualification to the statement's warning about low noise: hardness at a smaller noise rate can be transferred to a larger rate by deliberately adding noise, with the same source assumptions and appropriate sample accounting. This elementary implication is proved below. What is missing from the selected task is an adequate worst-case source theorem, not an impossibility of increasing the noise. The inherited formulation is preserved, but these logically different issues must be separated.

1. Matrix notation and the quantifiers.

For $N$ samples write \[ b=As+e\in\mathbb F_2^N, \] where the rows of $A\in\mathbb F_2^{N\times n}$ are independent uniform vectors and the coordinates of $e$ are independent Bernoulli variables of parameter $\eta$. The secret may be fixed. In contrast, a worst-case decoding problem supplies an arbitrary matrix $A_0$ and a word $b_0$ subject to a specified distance promise. A reduction must state the allowed dimensions, distance or approximation promise, whether errors are adversarial or random, the oracle's search or decision guarantee, and how the original answer is recovered.

The phrase "both involve a noisy linear system" does not establish the needed distributional connection. LPN's uniform random matrix and independent coordinate errors are part of its promise, not heuristic properties of a difficult-looking instance.

2. Exact randomization of the secret alone.

Choose $u\in\mathbb F_2^n$ uniformly and independently, and replace each label by \[ b_i'=b_i+\langle a_i,u\rangle. \] Then $b'=A(s+u)+e$. The new secret is uniform, while the matrix and independent error distribution are unchanged. A solver that recovers a uniformly random secret under the LPN experiment therefore recovers any fixed secret with the same averaged success probability after this transformation, by subtracting $u$ from its answer.

This is a genuine random self-reduction in the secret parameter. It does not randomize a worst-case matrix: if one begins with $A_0$, the transformed matrix is still $A_0$. Similarly, applying an invertible change of secret coordinates changes a matrix from $A_0$ to $A_0U$ but preserves its column space. Randomizing coordinates inside a fixed code is not choosing a uniform random code.

3. Information-theoretic identifiability with polynomial samples.

Put $\rho=1-2\eta>0$. For a candidate $v$ define its empirical disagreement rate \[ D(v)=\frac1N\#\{i:b_i\ne\langle a_i,v\rangle\}. \] For $v=s$ this is the average of independent Bernoulli($\eta$) variables. For any fixed $v\ne s$, the bit $\langle a_i,s-v\rangle$ is uniform and independent of $e_i$, so its disagreement rate is an average of fair bits. Take threshold $\theta=(\eta+1/2)/2$. The distance from either mean to this threshold is $\rho/4$.

The elementary Hoeffding bound and a union bound give \[ \Pr\left(D(s)\ge\theta\text{ or some }v\ne s \text{ has }D(v)\le\theta\right) \le 2^n\exp(-N\rho^2/8). \] Thus $N\ge8\rho^{-2}(n\log2+\log(1/\delta))$ makes the right side at most $\delta$. An exhaustive search of all $2^n$ candidates then recovers the secret by minimizing $D(v)$ with that probability. The candidates' scores need not be independent; the union bound does not assume they are.

At fixed positive bias $\rho$, the sample requirement is polynomial, but the stated search takes exponential time. This establishes identifiability, not computational easiness or a worst-case hardness reduction. At $\eta=1/2$ the labels are completely independent of the secret and recovery is impossible even information-theoretically, which explains why the strict upper bound on $\eta$ matters.

4. Validating a proposed secret and distinguishing.

Suppose an algorithm outputs a candidate $v$ using one batch of samples. Test it using a fresh independent batch of $q$ samples. Accept it when its disagreement rate is below $\theta$. Conditional on a correct candidate the mean is $\eta$; conditional on any fixed wrong candidate it is $1/2$. Under the completely uniform-pair experiment it is also $1/2$, even if the candidate was chosen in a complicated way from the first batch.

The same concentration inequality bounds a mistaken validation by $\exp(-q\rho^2/8)$ in each direction. Consequently a search algorithm with a prescribed inverse-polynomial success lower bound gives a distinguisher with inverse-polynomial advantage. To amplify to bounded error, each repetition uses independent samples, fresh algorithmic randomness, and a fresh independent secret shift from the preceding self-reduction; undo that shift on the proposed secret before testing it on a fresh validation batch. The fresh shifts ensure that an average success guarantee over uniform secrets also amplifies when the original secret is fixed. With polynomially small validation error per repetition, this uses polynomial overhead at constant noise. The procedure must use the success lower bound to select the number of repetitions; an unspecified vanishing success probability is not automatically enough.

The fresh-sample condition is essential. Testing on the samples used to select $v$ can reward overfitting. The implication proved is from search to distinguishing, with explicit validation; it is not a worst-case-to-average-case reduction and is not a proof of the converse direction.

5. Adding independent noise goes in a definite direction.

Let $0<\eta_1\le\eta_2<1/2$. Independently flip each label with probability \[ \delta=\frac{\eta_2-\eta_1}{1-2\eta_1}\in[0,1/2). \] If the old error is $e$ and the new flip is $z$, the error $e+z$ has probability \[ \eta_1(1-\delta)+(1-\eta_1)\delta=\eta_2. \] Different samples remain independent. Therefore a solver for noise $\eta_2$ can solve the lower-noise experiment at $\eta_1$ after this transformation. Uniform pairs remain uniform under the flips, so the same conversion applies to decision experiments. For efficiently samplable rational parameters it is exact; sufficiently precise sampling approximations can instead be controlled by total variation and the total sample count.

Accordingly, a hardness result at inverse-polynomial noise can imply constant-noise hardness under the same source hardness assumption. It does not strengthen a simultaneous decoding-and-dual-distinguishing assumption into hardness of an ordinary worst-case decoding problem. It also does not let an efficient low-noise solver solve a noisier input: reversing that direction would require removing unknown errors.

6. Why dense row mixing is not an iid-noise randomizer.

For a Bernoulli($\eta$) error vector $e\in\mathbb F_2^N$, independence gives the Fourier-character identity \[ \mathbb E(-1)^{\langle u,e\rangle}=\rho^{\operatorname{wt}(u)} \qquad(u\in\mathbb F_2^N). \] After an invertible row transformation $R$, the error is $Re$ and the corresponding expectation is $\rho^{\operatorname{wt}(R^{\mathsf T}u)}$. If $Re$ is to have exactly the original iid Bernoulli law, equality of these character expectations forces \[ \operatorname{wt}(R^{\mathsf T}u)=\operatorname{wt}(u) \quad\text{for every }u, \] because $0<\rho<1$. Taking $u$ to be each coordinate vector says every row of $R$ has weight one. Invertibility then forces the rows to select distinct coordinates, so $R$ is a permutation matrix. Conversely permutations preserve the law. This completely classifies invertible linear transformations preserving this iid noise distribution.

A small example already shows the problem. For two independent errors take $e'_1=e_1+e_2$ and $e'_2=e_2$. The first marginal has bias $\rho^2$, the second bias $\rho$, while the parity of the two outputs has bias $\rho$. Independence of the outputs would instead give bias $\rho^3$. These differ at every permitted noise rate.

Permutations can hide coordinate names, but they preserve the weight distribution and other invariants of a fixed code. General linear row transformations can mix a code much more thoroughly, but destroy the precise error distribution. A successful reduction needs a further argument overcoming this tension; no such argument follows just from linear algebra.

7. Fixed-weight noise, certificates and the remaining reduction.

Randomly permuting an adversarial error vector of weight $w$ produces the uniform distribution on the weight-$w$ layer. It does not produce independent Bernoulli errors: its total weight is deterministically $w$, whereas a Bernoulli vector has a binomial weight distribution. A mixture of layers with binomial weights could have the right law, but generating that mixture while retaining a recoverable solution to the supplied instance is another reduction step that must be proved.

The offline diagnostics enumerate all errors for small dimensions with exact rational noise probabilities. They verify the secret shift, the noise-increase formula, the Fourier identities, and the classification of noise-preserving invertible matrices through dimension three. They also record the explicit two-coordinate correlation obstruction. These are distribution identities, not empirical cryptographic evidence. The missing result remains a fully specified, efficient decoding reduction whose oracle inputs have the standard LPN law and whose outputs solve every promised source instance under the claimed source assumption.

Sources

• S1 Aggarwal, D., Gupta, R., Nguyen, H.H., Tan, K.Z., Vasudevan, P.N. $2026$. Towards Worst-case Hardness for Low-Noise LPN. IACR Cryptology ePrint Archive, Report 2026/1168. https://eprint.iacr.org/2026/1168. Formulation source.