LSN ⇒ LPN

Standard model · CIMR25

Statement

For constant code rate $\rho =k/n$ and noise parameter $\eta =1-\mu =o(1)$, hardness of $(k,n,\mu )$-LSN implies hardness of $(k,\eta )$-LPN with $m=k(1+\Omega (\eta ))$ samples (code dimension $k$, code length $m$, noise rate $\eta$) — CIMR25.