New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems
New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems
复制标题
DOI：
10.1109/jsait.2021.3053217
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Tao Guo;Ruida Zhou;C. Tian
中科院分区：
文献类型：
--
作者：
Tao Guo;Ruida Zhou;C. Tian
在私有信息检索（PIR）系统中，用户需要从一组存储服务器中检索可能的消息中的一个，但希望保持所请求的消息的身份对任何给定服务器是私有的。这方面的现有努力已经表明，检索的效率将受到服务器上允许的存储空间量的显著影响。在这项工作中，我们考虑的存储成本和检索成本之间的权衡。我们首先提出了三个基本结果：1）一个政权明智的近似特性的最佳权衡与一个因素的两个，2）循环置换引理，可以产生更复杂的代码从简单的基本代码，和3）放松熵线性规划（LP）下界，具有多项式的复杂性。配备循环置换引理，我们然后提出了两个新的码的结构，并通过应用引理，获得新的存储检索点。此外，我们通过以系统的方式仅利用松弛熵LP中的约束子集来推导出更明确的下界。虽然新的上界和下界并没有一致地导致更好的近似因子，但是在某些情况下，它们比现有技术明显更紧。
In a private information retrieval (PIR) system, the user needs to retrieve one of the possible messages from a set of storage servers, but wishes to keep the identity of the requested message private from any given server. Existing efforts in this area have made it clear that the efficiency of the retrieval will be impacted significantly by the amount of the storage space allowed at the servers. In this work, we consider the tradeoff between the storage cost and the retrieval cost. We first present three fundamental results: 1) a regime-wise approximate characterization of the optimal tradeoff with a factor of two, 2) a cyclic permutation lemma that can produce more sophisticated codes from simpler base codes, and 3) a relaxed entropic linear program (LP) lower bound that has a polynomial complexity. Equipped with the cyclic permutation lemma, we then propose two novel code constructions, and by applying the lemma, obtain new storage-retrieval points. Furthermore, we derive more explicit lower bounds by utilizing only a subset of the constraints in the relaxed entropic LP in a systematic manner. Though the new upper bound and lower bound do not lead to a better approximation factor uniformly, they are significantly tighter than the existing art in some regimes.