2-Server PIR with subpolynomial communication

Zeev Dvir, Sivakanth Gopi

Research output: Contribution to journalArticlepeer-review

27 Scopus citations

Abstract

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
Volume63
Issue number4
DOIs
StatePublished - Sep 2016

All Science Journal Classification (ASJC) codes

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

Keywords

  • Locally decodable codes
  • Private information retrieval

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

Cite this