Skip to main content

2-server PIR with sub-polynomial communication

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

To refer to this page use:
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 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.
Publication Date: 14-Jun-2015
Electronic Publication Date: 2015
Citation: Dvir, Z, Gopi, S. (2015). 2-server PIR with sub-polynomial communication. 14-17-June-2015 (577 - 584. doi:10.1145/2746539.2746546
DOI: doi:10.1145/2746539.2746546
Pages: 577 - 584
Type of Material: Conference Article
Journal/Proceeding Title: Proceeding STOC '15 Proceedings of the forty-seventh annual ACM symposium on Theory of computing
Version: Author's manuscript

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