Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al
Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al
复制标题
DOI：
10.1109/isit.2017.8006858
复制
发表时间：
2017-01
期刊：
影响因子：
--
通讯作者：
Hua Sun;S. Jafar
中科院分区：
文献类型：
--
作者：
Hua Sun;S. Jafar
MDS-TPIR问题的（K，N，T，Kc）实例由K个消息和N个分布式服务器组成。每个消息通过（N，Kc）MDS存储码单独编码。用户希望尽可能高效地检索一条消息，同时不向多达T个服务器的任何合谋集合透露关于所需消息索引的信息。检索效率的基本限制，即，MDS-TPIR的容量仅在T或Kc属于{1，N}的极端处是已知的。这项工作的重点是Freij-Hollanti，Gnilke，Hollanti和Karpuk最近提出的一个猜想，该猜想为MDS-TPIR提供了一个通用的容量表达式。我们证明了该猜想是假的作为一个反例提出的PIR计划的设置（K，N，T，Kc）=（2，4，2，2），它实现了3/5的速度，超过了限制容量，4/7。
A (K, N, T, Kc) instance of the MDS-TPIR problem is comprised of K messages and N distributed servers. Each message is separately encoded through an (N, Kc) MDS storage code. A user wishes to retrieve one message, as efficiently as possible, while revealing no information about the desired message index to any colluding set of up to T servers. The fundamental limit on the efficiency of retrieval, i.e., the capacity of MDS-TPIR is known only at the extremes where either T or Kc belongs to {1, N}. The focus of this work is a recent conjecture by Freij-Hollanti, Gnilke, Hollanti and Karpuk which offers a general capacity expression for MDS-TPIR. We prove that the conjecture is false by presenting as a counterexample a PIR scheme for the setting (K, N, T, Kc) = (2,4, 2, 2), which achieves the rate 3/5, exceeding the conjectured capacity, 4/7.