Information-Theoretic Private Information Retrieval: A Unified Construction
Information-Theoretic Private Information Retrieval: A Unified Construction
复制标题
信息论隐私信息检索：统一构建
DOI：
10.1007/3-540-48224-5_74
复制
发表时间：
2001
期刊：
影响因子：
--
通讯作者：
Yuval Ishai
中科院分区：
文献类型：
--
作者：
A. Beimel;Yuval Ishai
私有信息检索（Private Information Retrieval， PIR）协议使用户能够从数据库中检索数据项，同时隐藏被检索项的身份。在t-private， k-server PIR协议中，数据库在k个服务器之间复制，并且保护用户的隐私免受多达t个服务器的任何串通。这种协议的主要成本度量是检索单个数据位的通信复杂性。
A Private Information Retrieval (PIR) protocol enables a user to retrieve a data item from a database while hiding the identity of the item being retrieved. In a t-private, k-server PIR protocol the database is replicated among k servers, and the user's privacy is protected from any collusion of up to t servers. The main cost-measure of such protocols is the communication complexity of retrieving a single bit of data.
This work addresses the information-theoretic setting for PIR, in which the user's privacy should be unconditionally protected from collusions of servers. We present a unified general construction, whose abstract components can be instantiated to yield both old and new families of PIR protocols. A main ingredient in the new protocols is a generalization of a solution by Babai, Kimmel, and Lokam to a communication complexity problem in the so-called simultaneous messages model.
Our construction strictly improves upon previous constructions and resolves some previous anomalies. In particular, we obtain: (1) t-private k-server PIR protocols with O(n1/ċ(2kċ 1)/tċ) communication bits, where n is the database size. For t > 1, this is a substantial asymptotic improvement over the previous state of the art; (2) a constant-factor improvement in the communication complexity of 1-private PIR, providing the first improvement to the 2-server case since PIR protocols were introduced; (3) efficient PIR protocols with logarithmic query length. The latter protocols have applications to the construction of efficient families of locally decodable codes over large alphabets and to PIR protocols with reduced work by the servers.