LSN ⇒ Secret-Key PIR (SK-PIR)

Standard model · CIMR25

Statement

If the $(k,n,\mu )$-LSN assumption holds at constant code rate $k/n$ and noise $\mu =1-o(1)$, then for every constant $\epsilon >0$ there is a secret-key PIR scheme for $N$-bit databases with communication $O(N^{\epsilon })$, encoding size $(1+\epsilon )N$, and a server implementable by a Boolean circuit of size $(4+\epsilon )N$ — CIMR25.

Notes

• LSN is due to DKL09; CIMR25 conjecture its hardness in the new regime $k\ge \rho n$ and $\mu \ge 1-o(1)$, for every constant $0<\rho <1$ — CIMR25.
• From high-noise LPN, the same paper obtains SK-PIR with $O(N^{\epsilon })$ communication — CIMR25 (High-noise LPN ⇒ Secret-Key PIR (SK-PIR)).