Private Information Retrieval over Non-MDS Linear Codes

27 concepts9 papers1 proposal

When you download a file from a distributed storage system, the hosting servers naturally learn which file you wanted. Private Information Retrieval (PIR) protocols prevent this by structuring queries such that no individual server can deduce the identity of the requested file.

For years, the gold standard for achieving maximum download efficiency—known as the MDS-PIR capacity—was thought to require Maximum Distance Separable (MDS) codes. MDS codes (like Reed-Solomon codes) offer optimal storage-to-fault-tolerance trade-offs, but they are computationally rigid and expensive to repair when a server goes down. Modern distributed storage systems prefer more flexible, non-MDS linear codes, such as Locally Repairable Codes (LRCs), cyclic codes, or Reed-Muller codes.

A recent wave of research has shattered the assumption that MDS codes are required for optimal privacy. Instead, researchers have shown that the internal algebraic structure of non-MDS linear codes can be exploited to achieve the exact same theoretical PIR capacity limits.


The Core Intuition: Symmetries and Automorphisms

To understand why non-MDS codes can achieve optimal PIR capacity, we must look at how a PIR protocol hides a user's request. In a typical multi-server PIR protocol, a user requests a mixture of the desired file and random "noise" files. Privacy is maintained if the query sent to any single server looks completely random and independent of the target file index.

In MDS codes, this randomness is easy to distribute because every server holds an structurally identical piece of the data puzzle. However, Lin et al. and Kumar et al. demonstrated that the strict distance properties of MDS codes are a sufficient, but not a necessary, condition for this balancing act. What actually matters is structural symmetry.

If a linear code possesses a rich set of automorphisms—meaning the code remains invariant under specific permutations of its coordinates—the user can construct query sampling matrices that map perfectly to these symmetries. The internal symmetries allow the system to mask the user's request within noise that cancels out cleanly during the reconstruction phase. As a result, common symmetric code families like cyclic codes and Reed-Muller codes inherently satisfy the conditions to reach maximum PIR efficiency.

[User Request] ---> [Exploit Code Automorphisms] ---> [Symmetric Queries to Servers]
                                                                |
[Perfect Privacy] <--- [Noise Cancels Out Algebraically] <-------+

Breaking the Symmetry of Downloads

While the underlying code must possess structural symmetry to hide the query, the download protocol itself does not have to be symmetric. In fact, forcing every server to return the same amount of data is highly inefficient for non-MDS codes.

Non-MDS codes, such as Locally Repairable Codes (LRCs), often have an asymmetric layout by design: some bits are dedicated to local parities (for fast, cheap repairs), while others handle global parities. In Asymmetry Helps: Improved Private Information Retrieval Protocols for Distributed Storage, Lin et al. proved that by allowing different storage nodes to return different amounts of data, the protocol can accommodate the uneven structural layout of the code.

By aligning the local and global parities with the query requirements, Kumar et al. demonstrated that LRCs can successfully achieve the theoretical maximum MDS-PIR capacity. Users no longer have to choose between a system that is easy to maintain (LRCs) and one that is highly efficient for private browsing.


Quantifying Efficiency via Code Decomposition

How do we determine the exact maximum PIR rate a specific linear code can support? The answer lies in its sub-structures.

Lin et al. introduced a framework to break down complex linear codes into smaller, more manageable "punctured subcodes." They discovered a direct mathematical bridge between a code's Generalized Hamming Weights (GHWs)—which measure the structural strength and distance properties of its subcodes—and its optimal PIR rate.

Specifically, the authors showed that the maximum ratio of a subcode's dimension to its generalized Hamming weight dictates the upper bound of the retrieval rate. This insight simplifies protocol design: instead of searching an exponential space of query matrices, engineers can calculate the fundamental algebraic properties of the code's sub-structures to find the optimal retrieval strategy. To analyze the minimum message size required for these efficient systems, Guo et al. utilized "uniformly decomposable codes" as a representational strategy to map out the fundamental limits of data overhead.


Pushing Beyond Linearity

While linear codes dominate practical distributed storage due to their simplicity, the theoretical boundaries of the storage-retrieval trade-off continue to expand. Moving beyond linear combinations entirely, Tian et al. explored non-linear Shannon-theoretic coding schemes.

For a canonical two-message, two-database PIR system, the authors demonstrated that non-linear codes can achieve a storage rate of approximately 1.4387 at an optimal retrieval rate of 0.75—surpassing the absolute limits of the best possible linear codes, which require a storage rate of 1.5. This indicates that while exploiting the symmetries of linear codes solves today's practical constraints, non-linear constructions hold the key to the absolute physical limits of private data systems.

Key Foundational Work

An MDS-PIR Capacity-Achieving Protocol for Distributed Storage Using Non-MDS Linear Codes (2018) — contributed 8 concept elements to this direction.
An MDS-PIR Capacity-Achieving Protocol for Distributed Storage Using Non-MDS Linear Codes (2018) — contributed 4 concept elements to this direction.
Private Information Retrieval in Distributed Storage Systems Using an Arbitrary Linear Code (2016) — contributed 2 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_uniformly_decomposable_linear_codes_2927462c,
  title = {uniformly decomposable linear codes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uniformly-decomposable-linear-codes/rdr_2927462cc8004009a1d295d3f5499d8a},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_uniformly_decomposable_linear_codes_2927462c_v1,
  title = {uniformly decomposable linear codes},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/uniformly-decomposable-linear-codes/rdr_2927462cc8004009a1d295d3f5499d8a/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake