A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the  i th bit of an  n -bit database replicated among two noncommunicating servers, while not revealing any information about  i  to either server. In this work, we construct a 2-server PIR scheme with total communication cost  n O  (sflog log  n  log  n ). This improves over current 2-server protocols, which all require Ω( n  1/3 ) communication. Our construction circumvents the  n  1/3  barrier of Razborov and Yekhanin [2007], which holds for the restricted model of bilinear group-based schemes (covering all previous 2-server schemes). The 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.
['Zeev Dvir', 'Sivakanth Gopi']
2-Server PIR with Subpolynomial Communication