Private Information Retrieval from Joint Systematic MDS-Coded with Non-Colluding Servers: Bounds and Constructions
2026-06-22 • Information Theory
Information Theory
AI summaryⓘ
The authors study a system where data is stored across multiple servers using special codes (MDS codes) to protect data and allow private retrieval. They focus on joint MDS-coded private information retrieval (PIR), which helps users fetch files without revealing which file they want, improving on previous separate schemes. They find new upper limits on how efficiently this can be done and propose specific schemes that outperform earlier methods in certain cases, especially when the number of files and servers meet specific conditions. Their work shows notable improvements in retrieval speed, with gains increasing as the number of files grows.
Distributed storagePrivate Information Retrieval (PIR)MDS codesJoint MDS-coded PIRSystematic MDS array codesRetrieval rateCapacity boundsStorage rateFile sizeData privacy
Authors
Jingke Xu, Lirong Shi, Peng Lan, Weijun Fang
Abstract
Consider a distributed storage system consisting of $N$ non-colluding servers that collectively store a database of $M$ files encoded using an $[N,K]$ maximum distance separable(MDS) code. A user wishes to retrieve one file privately by accessing the servers without revealing the identity of the requested file. A scheme designed for this purpose is called a joint MDS-coded private information retrieval(PIR) scheme, which was first introduced by Sun and Tian in 2019 to break the capacity $\frac{1-K/N}{1-(K/N)^M}$ of the separate MDS-coded PIR schemes established by Banawan and Ulukus. However, the capacity of joint MDS-coded PIR remains largely unexplored. In this paper, we study the capacity of joint MDS-coded PIR with systematic MDS array storage codes under prescribed storage patterns. Specifically, we first derive upper bounds on the capacity of joint MDS-coded PIR for $K=Mt$ and $K=Mt+1$, respectively. We then construct three joint MDS-coded PIR schemes for the cases $N\le K+t, K=Mt$, $N>K+t, K=Mt$ and $N\le K+t, K=Mt+1$. The proposed schemes require small file sizes and achieve higher retrieval rates: the first and third schemes exceed the capacity of separate MDS-coded PIR schemes, while the second scheme does so when the storage rate $\frac{K}{N}>r_M$ for some $0<r_M<\frac{M}{M+1}$. In particular, for $K=Mt$ and $N\leq K+t$, the proposed scheme achieves the derived upper bound, thereby establishing that the optimal joint MDS-coded PIR capacity under the considered storage pattern is $1-(1-\frac{1}{M})\frac{K}{N}$. Compared with capacity-achieving separate MDS-coded PIR schemes at the same storage-code rate, the proposed schemes may achieve a substantial relative retrieval-rate improvement: the maximum improvement can exceed $15\%$ when $M\geq 4$, exceed $20\%$ when $M\geq 9$, and asymptotically approach $1-2/e\approx 26.42\%$ as M increases.