2-Server PIR with Sub-Polynomial Communication

被引：41
作者：
Dvir, Zeev [1 ,2 ]
Gopi, Sivakanth [1 ]
机构：
[1] Princeton Univ, Dept Comp Sci, Princeton, NJ 08544 USA
[2] Princeton Univ, Dept Math, Princeton, NJ 08544 USA
来源：
STOC'15: PROCEEDINGS OF THE 2015 ACM SYMPOSIUM ON THEORY OF COMPUTING | 2015年
关键词：
Private Information Retrieval; Locally Decodable Codes; LOCALLY DECODABLE CODES;
D O I：
10.1145/2746539.2746546
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
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 comog log rt. munication cost n(O)(root log log n/log n). This improves over current 2-server protocols which all require Omega(n(1/3)) communication. Our construction circumvents the n(1/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.
引用
收藏
页码：577 / 584
页数：8
相关论文
共 25 条
[1]  
Ambainis A., 1997, ICALP, P401
[2]  
[Anonymous], 2005, ICALP
[3]  
Beimel A, 2002, ANN IEEE SYMP FOUND, P261, DOI 10.1109/SFCS.2002.1181949
[4]  
BEIMEL A, 2001, ICALP, V2076, P912
[5]  
Bhowmick A, 2013, STOC'13: PROCEEDINGS OF THE 2013 ACM SYMPOSIUM ON THEORY OF COMPUTING, P823
[6]   Query-Efficient Locally Decodable Codes of Subexponential Length [J].
Chee, Yeow Meng ;
Feng, Tao ;
Ling, San ;
Wang, Huaxiong ;
Zhang, Liang Feng .
COMPUTATIONAL COMPLEXITY, 2013, 22 (01) :159-189
[7]   Private information retrieval [J].
Chor, B ;
Goldreich, O ;
Kushilevitz, E ;
Sudan, M .
JOURNAL OF THE ACM, 1998, 45 (06) :965-982
[8]  
Dvir Z., APPROXIMATION RANDOM, V8096, P513
[9]   Matching Vector Codes [J].
Dvir, Zeev ;
Gopalan, Parikshit ;
Yekhanin, Sergey .
2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2010, :705-714
[10]  
Efremenko K, 2009, ACM S THEORY COMPUT, P39
123