2-Server PIR with sub-polynomial communication

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({\sqrt{\log\log n/\log 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) (opens in new tab) and Zeev’s TCS+ talk (opens in new tab)