General constructions for information-theoretic private information retrieval

Our protocols simplify and improve upon previous ones, and resolve some previous anomalies. In particular, we get (1) 1-private k-server PIR protocols with O(k3n1/(2k-1)) communication bits, where n is the database size; (2) t-private k-server protocols with O(n1/⌊(2k-1)/t⌋) communication bits, for any constant integers k>t⩾1; and (3) t-private k-server protocols in which the user sends O(logn) bits to each server and receives O(nt/k+ε) bits in return, for any constant integers k>t⩾1 and constant ε>0. The latter protocols have applications to the construction of efficient families of locally decodable codes over large alphabets and to PIR protocols with reduced work by the servers.