TDH ⇒ cPIR

Standard model · DGI+19

Statement

A trapdoor hash function with one-bit hints gives two-message rate-1 string OT, and rate-1 OT gives single-server PIR; with the DDH- and QR-based trapdoor hash functions this is PIR with communication $\mathrm{polylog}(L)$ for a database of size $L$ — DGI+19. The communication is governed by the hash function’s compression: the trapdoor hash function of AMR25, the first from LPN, rests on quasi-polynomial hardness of low-noise LPN in dimension $k$ with noise rate $\epsilon =O({\log }^{1+\beta }(k)/k)$, $\beta >0$ (Low-noise LPN ⇒ TDH), has compression factor $2^{\Theta ({\log }^{1-\beta }\lambda )}$, and gives communication $L/2^{\Theta ({\log }^{1-\beta }L)}$, the first $o(L)$ PIR from a code-based assumption.