A General Coding Framework for Adaptive Private Information Retrieval
Jinbao Zhu, Xiaohu Tang · IEEE Transactions on Information Theory · 2025
The problem ofT-colluding private information retrieval (PIR) enables the user to retrieve one out ofMfiles from a distributed storage system withNservers without revealing anything about the index of the desired file to any group of up toTcolluding servers. In the considered storage system, theMfiles are stored across theNdistributed servers in anX-secureK-coded manner such that any group of up toXcolluding servers learns nothing about the files; the storage overhead at each server is reduced by a factor of 1/Kcompared to the total size of the files; and the files can be reconstructed from anyK+Xservers. However, in practical scenarios, when the user retrieves the desired file from the distributed system, some servers may respond to the user very slowly or not respond at all. These servers are referred to asstragglers, and particularly their identities and numbers are unknown in advance and may change over time. This paper considers the adaptive PIR problem that can be capable of tolerating the presence of a varying number of stragglers. We propose a general coding method for designing adaptive PIR schemes by introducing the concept of afeasible PIR coding framework. We demonstrate that anyfeasible PIR coding frameworkover a finite field Fqwith sizeqcan be used to construct an adaptive PIR scheme that achieves a retrieval rate of 1 −K+X+T−1/N−Ssimultaneously for all numbers of stragglers 0 ≤S≤N−(K+X+T) over the same finite field. Additionally, we provide an implementation of thefeasible PIR coding framework, ensuring that the adaptive PIR scheme operates over any finite field Fqwith sizeq≥N+max{K,N−(K+X+T−1)}.