Mid-noise LPN ⇒ High-noise LPN

Fully-black-box reduction · standard model · folklore · security loss: tight: advantage-preserving, one oracle call

Statement

If $(k,\epsilon )$-LPN is hard at noise rate $\epsilon =k^{-\gamma }$ for a constant $1/2\le \gamma <1$ (the mid-noise regime), then $(k,{\epsilon }^{\prime })$-LPN is hard at noise rate ${\epsilon }^{\prime }=k^{-{\gamma }^{\prime }}$ for every constant $0<{\gamma }^{\prime }<1/2$ (the high-noise regime): $\epsilon <{\epsilon }^{\prime }$, and LPN hardness is monotone in the noise rate — folklore.

Sketch

Map an instance $(\mathbf{A},\mathbf{v})$ to $(\mathbf{A},\mathbf{v}+{\mathbf{e}}^{\prime })$ with ${\mathbf{e}}^{\prime }\stackrel{\$}{\leftarrow }\mathrm{Ber}(\tau {)}^m$ and $\tau =({\epsilon }^{\prime }-\epsilon )/(1-2\epsilon )$, so that each coordinate of $\mathbf{e}+{\mathbf{e}}^{\prime }$ is $1$ with probability $\epsilon (1-\tau )+\tau (1-\epsilon )={\epsilon }^{\prime }$. Rate-$\epsilon$ instances become rate-${\epsilon }^{\prime }$ instances with the same $\mathbf{A}$ and $\mathbf{s}$, and uniform $\mathbf{v}$ stays uniform, so a distinguisher for the noisier problem breaks the less noisy one with the same advantage; the same map works for search LPN.