A New Framework for Designing Polynomial Codes for Private Information Retrieval
Fatemeh Kazemi, Ningze Wang, Alex Sprintson, Rafael G. L. D’Oliveira · 2024
This paper presents a framework for designing Private Information Retrieval (PIR) schemes in settings where the data is stored in a coded form (using MDS codes) and in the presence of collusion between servers. The framework is based on polynomial codes and provides a simple and efficient way to construct PIR schemes for several PIR problems and a broad range of system parameters. We prove that our framework has the best-known download rate and achieves asymptotic capability for strictly linear PIR schemes. One of the distinguishing features of this framework is its simplicity and ease of implementation, making it an attractive choice for practical retrieval schemes. We demonstrate the flexibility of our framework by demonstrating its use in solving private linear computation problems.