Welcome to the resource topic for 2022/1206
Title:
On the Optimal Communication Complexity of Error-Correcting Multi-Server PIR
Authors: Reo Eriguchi, Kaoru Kurosawa, Koji Nuida
Abstract:An \ell-server Private Information Retrieval (PIR) scheme enables a client to retrieve a data item from a database replicated among \ell servers while hiding the identity of the item. It is called b-error-correcting if a client can correctly compute the data item even in the presence of b malicious servers. It is known that b-error correction is possible if and only if \ell>2b. In this paper, we first prove that if error correction is perfect, i.e., the client always corrects errors, the minimum communication cost of b-error-correcting \ell-server PIR is asymptotically equal to that of regular (\ell-2b)-server PIR as a function of the database size n. Secondly, we formalize a relaxed notion of statistical b-error-correcting PIR, which allows non-zero failure probability. We show that as a function of n, the minimum communication cost of statistical b-error-correcting \ell-server PIR is asymptotically equal to that of regular (\ell-b)-server one, which is at most that of (\ell-2b)-server one. Our main technical contribution is a generic construction of statistical b-error-correcting \ell-server PIR for any \ell>2b from regular (\ell-b)-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 \ell>2b.
ePrint: https://eprint.iacr.org/2022/1206
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .