High-noise LPN ⇒ Secret-Key PIR (SK-PIR)

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 PIR scheme for $N$-bit databases with communication $O(N^{\epsilon })$ — CIMR25.

Notes

• One-way functions alone give SK-PIR, at online communication $\tilde{O}(\sqrt{N})$ rather than $O(N^{\epsilon })$ — BM26 (OWF ⇒ Secret-Key PIR (SK-PIR)).
• Under LSN, the same paper achieves similar communication with encoding size $(1+\epsilon )N$ and a server circuit of size $(4+\epsilon )N$ — CIMR25 (LSN ⇒ Secret-Key PIR (SK-PIR)).