Two-Server Private Information Retrieval in Sublinear Time and Quasilinear Space

In this talk, we build two-server private information retrieval (PIR) that achieves information-theoretic security and strong double-efficiency guarantees. On a database of n > 10^6 bits, the servers store a preprocessed data structure of size 1.5 * sqrt(log n) * n bits and then answer each PIR query by probing 12 n^0.82 bits in this data structure. To our knowledge, this is the first information-theoretic PIR with any constant number of servers that has quasilinear server storage n^{1 + o(1)} and polynomially sublinear server time n^{1 - \Omega(1)}. We describe connections to new data structures and locally decodable codes.