2-Server PIR with sub-polynomial communication - Dvir, Zeev; Gopi, Sivakanth (Journal of the ACM (JACM), 2016)
A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the ith bit of an n-bit database replicated among two servers (which do not communicate) while not revealing any information about i to either server. In this work we construct a 1-round 2-server PIR with total communication cost n^[O([[n/n]])]. This improves over the currently known 2-server protocols which require O(n^[1/3]) communication and matches the communication cost of known 3-server PIR schemes. Our improvement comes from reducing the number of servers in existing protocols, based on Matching Vector Codes, from 3 or 4 servers to 2. This is achieved by viewing these protocols in an algebraic way (using polynomial interpolation) and extending them using partial derivatives. Talk at DIMACS workshop (Rutgers University) and Zeev's TCS+ talk
Conference version appeared in STOC 2015 where it was a cowinner of the best paper award.