2-Server PIR with subpolynomial communication

Zeev Dvir, Sivakanth Gopi

Research output: Contribution to journalArticlepeer-review

60 Scopus citations


A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the ith 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 no(√log log n/log n). This improves over current 2-server protocols, which all require Ω(n1/3) communication. Our construction circumvents the n1/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.

Original languageEnglish (US)
Article number39
JournalJournal of the ACM
Issue number4
StatePublished - Sep 2016

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence


  • Locally decodable codes
  • Private information retrieval


Dive into the research topics of '2-Server PIR with subpolynomial communication'. Together they form a unique fingerprint.

Cite this