PIR array codes with optimal PIR rates
PIR array codes with optimal PIR rates
复制标题
DOI：
10.1109/isit.2017.8007011
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
S. Blackburn;T. Etzion
中科院分区：
文献类型：
--
作者：
S. Blackburn;T. Etzion
最近有很多兴趣在私人信息检索（PIR）的模型中，数据库存储在几个服务器上使用编码技术从分布式存储，而不是简单地复制。特别是，Fazelli，Vardy和Yaakobi最近的突破性成果引入了PIR码和PIR数组码的概念，并使用此概念来产生有效的协议。在本文中，我们感兴趣的是设计PIR阵列码。我们考虑有m台服务器的情况，每台服务器存储数据库位的一部分（1/s）;这里s是一个固定的有理数，s > 1。我们研究了具有k-PIR属性的PIR阵列码的最大PIR速率（这使得k服务器PIR协议能够在m服务器上仿真），其中PIR速率被定义为k/m。我们提出了上界的可实现的速率，一些建设，以及如何获得PIR阵列码的最高可能的PIR率的想法。特别地，我们提出了渐近满足我们的上界的构造，并且当1 < s ≤ 2时获得了精确的最大PIR率。
There has been much recent interest in Private information Retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient protocols. In this paper we are interested in designing PIR array codes. We consider the case when we have m servers, with each server storing a fraction (1/s) of the bits of the database; here s is a fixed rational number with s > 1. We study the maximum PIR rate of a PIR array code with the k-PIR property (which enables a k-server PIR protocol to be emulated on the m servers), where the PIR rate is defined to be k/m. We present upper bounds on the achievable rate, some constructions, and ideas how to obtain PIR array codes with the highest possible PIR rate. In particular, we present constructions that asymptotically meet our upper bounds, and the exact largest PIR rate is obtained when 1 < s ≤ 2.