期刊
JOURNAL OF THE ACM
卷 63, 期 4, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2968443
关键词
Private information retrieval; locally decodable codes
类别
资金
- NSF [CCF-1523816]
- Sloan fellowship
- Division of Computing and Communication Foundations
- Direct For Computer & Info Scie & Enginr [1523816] Funding Source: National Science Foundation
A 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 n (O)(root loglog 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 [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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据