k-server Byzantine-Resistant PIR Scheme with Optimal Download Rate and Optimal File Size
Stanislav Kruglik, Son Hoang Dau, Han Mao Kiah, Huaxiong Wang · 2023
We consider the problem of designing a Private Information Retrieval (PIR) scheme on m files replicated on k servers that can collude or, even worse, can return incorrect answers. Our goal is to correctly retrieve a specific message while keeping its identity private from the database servers. We consider the asymptotic information-theoretic capacity of this problem defined as the maximum ratio of the number of correctly retrieved symbols to the downloaded one for a large enough number of stored files. We propose an achievable scheme with a small file size and prove that such a file size is minimal for the fixed number of retrieved symbols, solving the problem pointed out by Banawan and Ulukus.A full version [1] of this paper is accessible at: https://arxiv.org/abs/2302.02230