Computer Science/Discrete Mathematics Seminar I
10:30am|Simonyi Hall 101 and Remote Access
Topic: Improved Private Information Retrieval Schemes from Matching Vectors and Derivatives
Speaker: Swastik Kopparty
Affiliation: University of Toronto
Date: March 31, 2025
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.