Access Restriction

Author Dvir, Zeev ♦ Gopi, Sivakanth
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Private information retrieval ♦ Locally decodable codes
Abstract A 2-server Private Information Retrieval (PIR) scheme allows a user to retrieve the $\textit{i}th$ bit of an $\textit{n}-bit$ database replicated among two noncommunicating servers, while not revealing any information about $\textit{i}$ to either server. In this work, we construct a 2-server PIR scheme with total communication cost $n^{O}(&sqrt;&frac;log$ log $\textit{n}$ log $\textit{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.
Description Author Affiliation: Princeton University, NJ, USA (Dvir, Zeev; Gopi, Sivakanth)
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 4
Page Count 15
Starting Page 1
Ending Page 15

Open content in new tab

   Open content in new tab
Source: ACM Digital Library