Multi-Server PIR with Full Error Detection and Limited Error Correction

An ℓ-server Private Information Retrieval (PIR) scheme allows a client to retrieve the τ-th element aτ from a database a = (a1,..., an) which is replicated among ℓ servers. It is called t-private if any coalition of t servers learns no information on τ, and b-error correcting if a client can correctly compute aτ from ℓ answers containing b errors. This paper concerns the following problems: Is there a t-private ℓ-server PIR scheme with communication complexity o(n) such that a client can detect errors with probability 1 − ϵ even if ℓ − 1 servers return false answers? Is it possible to add error correction capability to it? We first formalize a notion of (1 − ϵ)-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., ϵ = 0) PIR scheme with o(n) communication. Next, for ϵ > 0, we construct 1-private (1 − ϵ)-fully error detecting and (ℓ/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 ≥ 2 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.