2-server PIR with sub-polynomial communication

Zeev Dvir, Sivakanth Gopi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

40 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 non-communicating 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 [21] 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)
Title of host publicationSTOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Number of pages8
ISBN (Electronic)9781450335362
StatePublished - Jun 14 2015
Event47th Annual ACM Symposium on Theory of Computing, STOC 2015 - Portland, United States
Duration: Jun 14 2015Jun 17 2015

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017


Other47th Annual ACM Symposium on Theory of Computing, STOC 2015
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Software


  • Locally Decodable Codes
  • Private Information Retrieval


Dive into the research topics of '2-server PIR with sub-polynomial communication'. Together they form a unique fingerprint.

Cite this