论文标题
关于私人信息检索系统中存储回程权衡的新结果
New Results on the Storage-Retrieval Tradeoff in Private Information Retrieval Systems
论文作者
论文摘要
在私人信息检索（PIR）系统中，用户需要从一组存储服务器中检索可能的消息之一，但希望将所请求的消息的身份从任何给定的服务器私有。该领域的现有努力清楚地表明，检索的效率将受到服务器允许的存储空间数量的重大影响。在这项工作中，我们考虑存储成本与检索成本之间的权衡。我们首先提出三个基本结果：1）最佳权衡方面的制度2-鉴定表征，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 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 2-approximate characterization of the optimal tradeoff, 2) a cyclic permutation lemma that can produce more sophisticated codes from simpler ones, 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 more precise approximate characterization in general, they are significantly tighter than the existing art.
