Skip to main content

2-Server PIR with subpolynomial communication

Author(s): Dvir, Zeev; Gopi, Sivakanth

To refer to this page use:
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDvir, Zeev-
dc.contributor.authorGopi, Sivakanth-
dc.identifier.citationDvir, Z, Gopi, S. (2016). 2-Server PIR with subpolynomial communication. Journal of the ACM, 63 (10.1145/2968443en_US
dc.description.abstractA 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.en_US
dc.relation.ispartofJournal of the ACMen_US
dc.rightsAuthor's manuscripten_US
dc.title2-Server PIR with subpolynomial communicationen_US
dc.typeJournal Articleen_US

Files in This Item:
File Description SizeFormat 
2-server PIR with sub-polynomial communication.pdf195.01 kBAdobe PDFView/Download

Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.