Welcome to the resource topic for 2022/500
Title:
Multi-Server PIR with Full Error Detection and Limited Error Correction
Authors: Reo Eriguchi, Kaoru Kurosawa, Koji Nuida
Abstract:An \ell-server Private Information Retrieval (PIR) scheme allows a client to retrieve the \tau-th element a_\tau from a database \bm{a}=(a_1,\ldots,a_n) which is replicated among \ell servers. It is called t-private if any coalition of t servers learns no information on \tau, and b-error correcting if a client can correctly compute a_\tau from \ell answers containing b errors. This paper concerns the following problems: Is there a t-private \ell-server PIR scheme with communication complexity o(n) such that a client can detect errors with probability 1-\epsilon even if \ell-1 servers return false answers? Is it possible to add error correction capability to it? We first formalize a notion of (1-\epsilon)-fully error detecting PIR in such a way that an answer returned by any malicious server depends on at most t queries, which reflects t-privacy. We then prove an impossibility result that there exists no 1-fully error detecting (i.e., \epsilon=0) PIR scheme with o(n) communication. Next, for \epsilon>0, we construct 1-private (1-\epsilon)-fully error detecting and (\ell/2-O(1))-error correcting PIR schemes which have n^{o(1)} communication, and a t-private one which has O(n^{c}) communication for any t\geq2 and some constant c<1. Technically, we show generic transformation methods to add error correction capability to a basic fully error detecting PIR scheme. We also construct such basic schemes by modifying certain existing PIR schemes which have no error detection capability.
ePrint: https://eprint.iacr.org/2022/500
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 .