Low-noise LPN ⇒ TDH

Standard model · AMR25 · security loss: requires quasi-polynomial hardness of low-noise LPN

Statement

Quasi-polynomial hardness of low-noise LPN in dimension $k$ with noise rate $\epsilon =O({\log }^{1+\beta }(k)/k)$, for a constant $\beta >0$, implies trapdoor hash functions with compression factor $2^{\Theta ({\log }^{1-\beta }\lambda )}$; this is the first trapdoor hash function from LPN — AMR25.

Notes

• The trapdoor hash function gives single-server PIR with communication $L/2^{\Theta ({\log }^{1-\beta }L)}$ for a database of size $L$, the first PIR with communication $o(L)$ from a code-based assumption (TDH ⇒ cPIR) — AMR25.