Paper 2022/500

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

Reo Eriguchi, Kaoru Kurosawa, and 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 $\text{bm}a=(a_1,\dots ,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-ϵ$ 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-ϵ)$-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 $$-fully error detecting (i.e., $$) PIR scheme with $$ communication. Next, for $$, we construct $$-private $$-fully error detecting and $$-error correcting PIR schemes which have $$ communication, and a $$-private one which has $$ communication for any $$ and some constant $$. 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.