Improved Private Information Retrieval Schemes from Matching Vectors and Derivatives

Private Information Retrieval (PIR) is a method for a user to interact with t non-colluding servers and read some entry of a database of size n without revealing to the servers anything about which entry of the database was read. After a long line of work, including breakthroughs by Yekhanin (2007), Efremenko (2009) and Dvir-Gopi (2014), we know that for any t greater than or equal to 2, t-server PIR is possible with n^{o(1)} communication.

These are based on properties of polynomials as well as some unique geometric configurations of vectors in Z_m^k, with m composite.

In this talk, I will describe some ideas that go into these PIR schemes, and give a new, simpler PIR scheme for t = 2 based on a slightly different viewpoint on them. This simpler scheme generalizes well, and gives superpolynomial improvements to the best known communication for all but finitely many t. Notably, we get a 3-server PIR scheme with communication exp((log n)^(1/3)), improving upon the previously best-known communication of exp((log n)^(1/2)) due to Efremenko.

Joint work with Fatemeh Ghasemi and Madhu Sudan.