On the Optimal Communication Complexity of Error-Correcting Multi-Server PIR
On the Optimal Communication Complexity of Error-Correcting Multi-Server PIR
复制标题
纠错多服务器PIR的最优通信复杂度
DOI：
10.1007/978-3-031-22368-6_3
复制
发表时间：
2022
期刊：
影响因子：
--
通讯作者：
Koji Nuida
中科院分区：
文献类型：
--
作者：
Reo Eriguchi;Kaoru Kurosawa;Koji Nuida
服务器私有信息检索（PIR）方案使客户端能够从数据库复制的服务器中检索数据项，同时隐藏项的身份。如果客户端即使在存在恶意服务器的情况下也能正确地计算数据项，则称为b错误校正。已知b-纠错是可能的，当且仅当。在本文中，我们首先证明，如果纠错是完美的，即，由于客户端总是纠错，纠错服务器PIR的最小通信开销与正常服务器PIR的最小通信开销作为数据库大小的函数渐近相等。其次，我们正式提出了一个宽松的概念，允许非零的故障概率的非零错误校正PIR。我们表明，作为一个函数的n，最小的通信成本的adverticalb-error-correcting-server的PIR是渐近等于常规的服务器，这是最多的服务器之一。我们的主要技术贡献是一个通用的构造的反错误校正服务器PIR的任何从常规服务器PIR。因此，我们可以减少的问题，确定最佳的通信复杂性的纠错PIR确定定期PIR。特别是，我们的建设实例化与国家的最先进的PIR计划和以前的单服务器PIR的下限导致在分离的完美和统计纠错之间的通信成本。
An-server Private Information Retrieval (PIR) scheme enables a client to retrieve a data item from a database replicated amongservers while hiding the identity of the item. It is calledb-error-correcting if a client can correctly compute the data item even in the presence ofbmalicious servers. It is known thatb-error correction is possible if and only if. In this paper, we first prove that if error correction is perfect, i.e., the client always corrects errors, the minimum communication cost ofb-error-correcting-server PIR is asymptotically equal to that of regular-server PIR as a function of the database sizen. Secondly, we formalize a relaxed notion of statisticalb-error-correcting PIR, which allows non-zero failure probability. We show that as a function ofn, the minimum communication cost of statisticalb-error-correcting-server PIR is asymptotically equal to that of regular-server one, which is at most that of-server one. Our main technical contribution is a generic construction of statisticalb-error-correcting-server PIR for anyfrom regular-server PIR. We can therefore reduce the problem of determining the optimal communication complexity of error-correcting PIR to determining that of regular PIR. In particular, our construction instantiated with the state-of-the-art PIR schemes and the previous lower bound for single-server PIR result in a separation in terms of communication cost between perfect and statistical error correction for any.