High-noise LPN ⇒ SK-DEPIR

Standard model · CIMR25

Statement

If high-noise LPN is hard, at noise rate $k^{-\gamma }$ for a constant $0<\gamma <1/2$ (a regime not known to imply public-key encryption), then for every constant $\epsilon >0$ there is a secret-key DEPIR in a weak sense: communication is $O(N^{\epsilon })$ and the server reads $N/\mathrm{polylog}(N)$ bits of the encoded database per query — CIMR25.