🔢 mathematics

Private Information Retrieval from Joint Systematic MDS-Coded with Non-Colluding Servers: Bounds and Constructions

This paper investigates the capacity of joint MDS-coded private information retrieval (PIR) with systematic array codes under prescribed storage patterns, deriving upper bounds and constructing three schemes that achieve optimal rates for specific parameters and significantly outperform existing separate MDS-coded PIR schemes by up to 26.42% in retrieval efficiency.

Original authors: Jingke Xu, Lirong Shi, Peng Lan, Weijun Fang

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jingke Xu, Lirong Shi, Peng Lan, Weijun Fang

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a massive digital library containing M different books (files). This library isn't stored on one giant server; instead, it's split up and stored across N different servers (like different branches of a library). To save space and protect against data loss, the library uses a clever mathematical trick called MDS coding. Think of this like shredding the books into pieces and scattering the pieces across the branches, adding "redundant" pieces so that if you lose a few branches, you can still reconstruct the whole book from the remaining ones.

Here is the problem: You want to borrow one specific book without the librarians (the servers) knowing which book you want. If you just ask for "Book A," they know you want Book A. If you ask for "Book B," they know you want Book B. You need a way to ask for your book so that every librarian thinks you might be asking for any book with equal probability. This is called Private Information Retrieval (PIR).

The Old Way vs. The New Way

The Old Way (Separate Coding):
In previous methods, each book was encoded and stored independently. Imagine Book 1 is shredded and scattered, and Book 2 is shredded and scattered, but they don't mix. The researchers found a "speed limit" (called Capacity) for how efficiently you could download your book privately in this setup. It's like a speed limit sign saying, "You can only download 10 pages of your book for every 100 pages you download in total."

The New Way (Joint Coding):
This paper introduces a new strategy called Joint MDS-coded PIR. Instead of treating each book as a separate puzzle, the library mixes the pieces of all books together into one giant, interconnected puzzle before scattering them.

The Analogy: Imagine instead of putting Book 1's pieces in one box and Book 2's pieces in another, you mix a handful of pieces from Book 1 and a handful from Book 2 into a single bag, then scatter those bags.
The Result: Because the books are mixed together, the user can ask questions that "cancel out" the noise from the other books more efficiently. This allows the user to download their desired book faster (a higher retrieval rate) than the old speed limit allowed.

What This Paper Actually Did

The authors didn't just guess that this new way was better; they did the heavy math to prove it and built the actual blueprints.

They Set a New Speed Limit (Upper Bounds):
They calculated the absolute theoretical maximum efficiency for this new "mixed" system. They proved that for certain configurations (specifically when the number of servers and files follow a specific mathematical pattern), there is a hard ceiling on how fast you can go.
- Key Finding: They proved that a scheme proposed by other researchers (Sun and Tian) actually hits this ceiling perfectly in some cases. It's the fastest possible way to do it under those specific rules.
They Built the Blueprints (Constructions):
They designed three specific "recipes" (schemes) for how a user should ask for their book and how the servers should answer, covering different scenarios:
- Scenario A: When there are fewer servers than a certain threshold.
- Scenario B: When there are more servers.
- Scenario C: When the number of files is slightly different (not a perfect multiple).
- The Magic: In all three cases, their new recipes allow the user to download their book with less wasted data than the old "separate" methods.
How Much Better Is It?
The paper quantifies the improvement. It's not just a tiny bit faster; it's a significant jump.
- If you have 4 or more files, the new method is at least 15% more efficient.
- If you have 9 or more files, it's at least 20% more efficient.
- As the number of files gets very large, the efficiency gain approaches roughly 26.4%.
- Translation: In the old system, you might have to download 100 pages to get 10 pages of your book. In this new system, you might only need to download 75 pages to get those same 10 pages.

The "Secret Sauce"

The paper relies on a concept called Storage Patterns.

Think of the storage pattern as the "floor plan" of how the library arranges the mixed book pieces.
The authors focused on specific floor plans (called systematic MDS array codes) where the arrangement is predictable and structured.
By strictly defining this floor plan, they could mathematically prove that their new "Joint" method breaks the old speed limits.

Summary in Plain English

This paper solves a puzzle about how to secretly download a file from a distributed network of computers.

The Problem: Previous methods had a limit on how fast you could download without revealing your choice.
The Solution: By mixing the data of all files together before storing them (Joint Coding) rather than storing them separately, you can bypass that limit.
The Proof: The authors mathematically proved the new maximum speed limit and built working examples that reach it.
The Benefit: You can get your data significantly faster (up to ~26% more efficient) without the servers knowing what you asked for.

The paper stays strictly within the realm of information theory and coding; it does not claim to solve medical problems, financial issues, or other real-world applications beyond the theoretical efficiency of data retrieval. It is a "blueprint" for a more efficient digital library system.

Technical Summary: Private Information Retrieval from Joint Systematic MDS-Coded with Non-Colluding Servers

Problem Statement
This paper addresses the problem of Private Information Retrieval (PIR) in distributed storage systems where $M$ files are stored across $N$ non-colluding servers using an $[N, K]$ Maximum Distance Separable (MDS) code. Unlike traditional "separate" MDS-coded PIR schemes, where each file is encoded independently, this work focuses on joint MDS-coded PIR. In this model, all $M$ files are encoded together into a single codeword using a systematic MDS array code. The user wishes to retrieve a specific file $W_\theta$ without revealing the identity $\theta$ to any individual server.

The primary motivation stems from the observation by Sun and Tian [28] that joint encoding can break the capacity limits of separate MDS-coded PIR (established by Banawan and Ulukus [9]) in specific parameter regimes. However, the theoretical capacity of joint MDS-coded PIR remained largely unexplored, particularly regarding how storage patterns and systematic constraints affect achievable retrieval rates.

Methodology and System Model
The authors refine the system model by introducing two critical components:

Storage Pattern ( $P$ ): A matrix describing how the $M$ files are arranged into the $K$ systematic input blocks of the storage code.
Systematic MDS Array Code ( $C$ ): A code that encodes these blocks across $N$ servers.

The paper defines the capacity $C^{(s)}_{JMDS-PIR}(M, N, K, P)$ as the supremum of retrieval rates over all compatible systematic MDS array codes for a fixed storage pattern $P$ . The study focuses on two specific storage patterns:

Case 1: $K = Mt$ with pattern $P = \ell I_M \otimes \mathbf{1}_t$ .
Case 2: $K = Mt + 1$ with pattern $P = \frac{\ell}{M} (M I_M \otimes \mathbf{1}_t \mid \mathbf{1}_M^\top)$ .

To derive theoretical limits, the authors employ information-theoretic tools, specifically characterizing the conditional independence structure of server answers (Lemma 3) and deriving recursive inequalities based on Han's inequality (Lemmas 5 and 8). For construction, they utilize random permutations and linear combinations of stored symbols to ensure privacy while maximizing the download of useful information.

Key Contributions and Results

Upper Bounds on Capacity:
- For $K = Mt$ and pattern $P = \ell I_M \otimes \mathbf{1}_t$ , the authors derive an upper bound of $1 - (1 - \frac{1}{M})\frac{K}{N}$ .
- For $K = Mt + 1$ and pattern $P = \frac{\ell}{M} (M I_M \otimes \mathbf{1}_t \mid \mathbf{1}_M^\top)$ , they derive an upper bound of $\frac{K(N-K+t)}{(K-1)(N-1)}$ .
- Crucially, for the case $K = Mt$ and $N \le K + t$ , the derived upper bound matches the performance of schemes proposed by Sun and Tian [28], providing the first proof of their optimality under these specific storage patterns.
Scheme Constructions:
The paper constructs three joint systematic MDS-coded PIR schemes:
- Construction 1 ( $N \le K + t, K = Mt$ ): This scheme achieves the upper bound $1 - (1 - \frac{1}{M})\frac{K}{N}$ , thereby establishing the exact capacity for this regime.
- Construction 2 ($N > K + t, K = Mt$): This scheme achieves a retrieval rate of $\frac{N+K-t}{NM}$ .
- Construction 3 ( $N \le K + t, K = Mt + 1$ ): This scheme achieves a retrieval rate of $\frac{K(N-K+t)}{M((t+1)N-K)}$ .
Performance Improvements:
The proposed schemes are compared against capacity-achieving separate MDS-coded PIR schemes (e.g., [9], [17], [18]). The analysis shows that the joint schemes achieve strictly higher retrieval rates in specific parameter ranges:
- For $K = Mt$, the improvement is significant when the storage rate $r = K/N$ is high.
- For $K = Mt + 1$, the joint scheme always outperforms the separate scheme when $K < N \le K + t$ .
- Quantitative Gains: The relative retrieval-rate improvement can exceed 15% when $M \ge 4$ , exceed 20% when $M \ge 9$ , and asymptotically approach $1 - 2/e \approx 26.42\%$ as $M$ increases.
- Additionally, the proposed constructions require smaller file sizes and, in some cases (e.g., $M=2, N=3t$ ), significantly reduce the required finite field size compared to previous joint schemes [28].

Significance
The paper's primary significance lies in theoretically characterizing the capacity of joint systematic MDS-coded PIR under prescribed storage patterns, a problem previously open. By proving the optimality of Sun and Tian's [28] schemes for specific parameters and providing new constructions for broader parameter sets, the work demonstrates that joint encoding is not merely a heuristic but a provably superior strategy for PIR in distributed storage. The results confirm that joint MDS-coded PIR can break the capacity limits of separate coding, offering substantial gains in retrieval efficiency without compromising privacy, particularly as the number of files ( $M$ ) increases. The authors note that while their results cover specific parameter regimes, extending these findings to more general joint MDS-coded PIR settings remains a challenging direction for future research.

The Old Way vs. The New Way

What This Paper Actually Did

The "Secret Sauce"

Summary in Plain English

Technical Summary: Private Information Retrieval from Joint Systematic MDS-Coded with Non-Colluding Servers

More like this