TY - GEN
T1 - 2-server PIR with sub-polynomial communication
AU - Dvir, Zeev
AU - Gopi, Sivakanth
PY - 2015/6/14
Y1 - 2015/6/14
N2 - 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.
AB - 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.
KW - Locally Decodable Codes
KW - Private Information Retrieval
UR - http://www.scopus.com/inward/record.url?scp=84958779720&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958779720&partnerID=8YFLogxK
U2 - 10.1145/2746539.2746546
DO - 10.1145/2746539.2746546
M3 - Conference contribution
AN - SCOPUS:84958779720
T3 - Proceedings of the Annual ACM Symposium on Theory of Computing
SP - 577
EP - 584
BT - STOC 2015 - Proceedings of the 2015 ACM Symposium on Theory of Computing
PB - Association for Computing Machinery
T2 - 47th Annual ACM Symposium on Theory of Computing, STOC 2015
Y2 - 14 June 2015 through 17 June 2015
ER -