Paper 2022/500 Original: eprint.iacr.org/2022/500 ↗

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

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.