Paper 2022/1206

On the Optimal Communication Complexity of Error-Correcting Multi-Server PIR

Abstract

An $\ell$-server Private Information Retrieval (PIR) scheme enables a client to retrieve a data item from a database replicated among $\ell$ servers while hiding the identity of the item. It is called $b$-error-correcting if a client can correctly compute the data item even in the presence of $b$ malicious servers. It is known that $b$-error correction is possible if and only if $\ell >2b$. In this paper, we first prove that if error correction is perfect, i.e., the client always corrects errors, the minimum communication cost of $$-error-correcting $$-server PIR is asymptotically equal to that of regular $$-server PIR as a function of the database size $$. Secondly, we formalize a relaxed notion of statistical $$-error-correcting PIR, which allows non-zero failure probability. We show that as a function of $$, the minimum communication cost of statistical $$-error-correcting $$-server PIR is asymptotically equal to that of regular $$-server one, which is at most that of $$-server one. Our main technical contribution is a generic construction of statistical $$-error-correcting $$-server PIR for any $$ from regular $$-server PIR. We can therefore reduce the problem of determining the optimal communication complexity of error-correcting PIR to determining that of regular PIR. In particular, our construction instantiated with the state-of-the-art PIR schemes and the previous lower bound for single-server PIR result in a separation in terms of communication cost between perfect and statistical error correction for any $$.