Paper 2022/500

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

Reo Eriguchi, Kaoru Kurosawa, and Koji Nuida

Abstract

An $$-server Private Information Retrieval (PIR) scheme allows a client to retrieve the $$-th element $$ from a database $$ which is replicated among $$ servers. It is called $$-private if any coalition of $$ servers learns no information on $$, and $$-error correcting if a client can correctly compute $$ from $$ answers containing $$ errors. This paper concerns the following problems: Is there a $$-private $$-server PIR scheme with communication complexity $$ such that a client can detect errors with probability $$ even if $$ servers return false answers? Is it possible to add error correction capability to it? We first formalize a notion of $$-fully error detecting PIR in such a way that an answer returned by any malicious server depends on at most $$ queries, which reflects $$-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.