On the Optimal File Size of Capacity-Achieving Byzantine-Resistant Private Information Retrieval Schemes

We consider the problem of designing a Private Information Retrieval (PIR) scheme for <i>n</i> files replicated on <i>k</i> servers that can collude and return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We focus on minimizing download costs and propose PIR schemes with minimal download costs and the smallest file size (proportional to the number of involved servers). Motivated by the possible presence of stragglers, we extend our previous conference results and propose a scheme in which the number of participating servers may vary.