PIR Array Codes With Optimal Virtual Server Rate
PIR Array Codes With Optimal Virtual Server Rate
复制标题
DOI：
10.1109/tit.2019.2920975
复制
发表时间：
2016-07
影响因子：
2.5
通讯作者：
S. Blackburn;T. Etzion
中科院分区：
文献类型：
--
作者：
S. Blackburn;T. Etzion
最近有很多兴趣在私人信息检索（PIR）的模型中，数据库存储在几个服务器上使用编码技术从分布式存储，而不是简单地复制。特别是，Fazelli，Vardy和Yaakobi最近的突破性成果引入了PIR码和PIR数组码的概念，并使用此概念来产生有效的PIR协议。在本文中，我们感兴趣的是设计PIR阵列码。我们考虑当我们有$m$台服务器时的情况，每个服务器存储数据库位的一小部分$（1/s）$;这里$s$是一个固定的有理数，$s $> 1$。具有$k$ -PIR属性的PIR数组代码使$k$ -server PIR协议（具有$k\leq m$）能够在$m$server上仿真，从而降低了协议的总体存储需求。PIR协议的通信复杂度随着k的增加而降低，因此虚拟服务器速率（定义为k/m）是一个重要参数。研究了具有$k$ -PIR性质的PIR数组码的最大虚拟服务器速率.我们提出了上界可实现的虚拟服务器速率，一些建设，以及如何获得PIR阵列码的最高可能的虚拟服务器速率的想法。特别是，我们目前的建设，渐近满足我们的上界和确切的最大虚拟服务器速率时获得1美元。一个$k$ -PIR码（和类似的$k$ -PIR阵列码）也是一个具有符号可用性$k-1$的局部可修复码。这样的代码确保了每个信息符号的$k$并行读取。因此，虚拟服务器速率与代码用作本地可修复代码时的符号可用性非常密切相关。本文的结果进行了讨论，在这种情况下，子空间码也有一个重要的作用。
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 a 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 PIR 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$ . A PIR array code with the $k$ -PIR property enables a $k$ -server PIR protocol (with $k\leq m$ ) to be emulated on $m$ servers, with the overall storage requirements of the protocol being reduced. The communication complexity of a PIR protocol reduces as $k$ grows, so the virtual server rate, defined to be $k/m$ , is an important parameter. We study the maximum virtual server rate of a PIR array code with the $k$ -PIR property. We present upper bounds on the achievable virtual server rate, some constructions, and ideas how to obtain the PIR array codes with the highest possible virtual server rate. In particular, we present constructions that asymptotically meet our upper bounds and the exact largest virtual server rate is obtained when $1 . A $k$ -PIR code (and similarly a $k$ -PIR array code) is also a locally repairable code with symbol availability $k-1$ . Such a code ensures $k$ parallel reads for each information symbol. So the virtual server rate is very closely related to the symbol availability of the code when used as a locally repairable code. The results of this paper are discussed also in this context where subspace codes also have an important role.