Paper 2022/500

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

Reo Eriguchi, Kaoru Kurosawa, and Koji Nuida


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Major revision. 3rd Conference on Information-Theoretic Cryptography (ITC 2022)
Private Information Retrieval
Contact author(s)
reo-eriguchi @ g ecc u-tokyo ac jp
2022-04-28: received
Short URL
Creative Commons Attribution


      author = {Reo Eriguchi and Kaoru Kurosawa and Koji Nuida},
      title = {Multi-Server {PIR}  with Full Error Detection and Limited Error Correction},
      howpublished = {Cryptology ePrint Archive, Paper 2022/500},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.