🔢 mathematics

Weak Private Information Retrieval for Graph-based Storage

This paper introduces and formally studies Graph-based Weak Private Information Retrieval (G-WPIR) for distributed storage systems with graph-based replication, proposing a scheme that achieves a smooth trade-off between retrieval rate and privacy leakage (measured by mutual information and maximal leakage) under minimal subpacketization for arbitrary, complete, and complete bipartite graphs.

Original authors: Shodasakshari Vidya, Chandan Anand, Prasad Krishnan

Published 2026-07-24

📖 8 min read🧠 Deep dive

CC BY 4.0

Original authors: Shodasakshari Vidya, Chandan Anand, Prasad Krishnan

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 are at a massive, chaotic library where every book is stored in two different locations simultaneously. You want to borrow a specific book, but you have a strict rule: you cannot let the librarian at either location know which book you are looking for. If they know, they might start guessing your reading habits, selling your data, or even hiding the book from you. This is the world of Private Information Retrieval (PIR). In the real world, this is how we keep our search history, medical records, or financial data safe when we ask a network of computers for information. The goal is to get the answer without giving away the "question."

However, there's a catch. To hide your question, you usually have to ask for a lot of extra, useless information (like asking for every book in the library just to make it look like you might want any of them). This is slow and wasteful. For a long time, scientists thought you had to choose between being 100% invisible (perfect privacy) or being fast (high speed). You couldn't have both. But what if you were willing to let the librarians peek at your request just a tiny bit? What if you could trade a little bit of privacy for a huge boost in speed? This is the question this paper tackles. It explores a middle ground called "Weak Private Information Retrieval," asking: How much faster can we go if we allow a tiny, controlled amount of information to leak?

The Story of the Graph Library

The authors of this paper, Shodasakshari Vidya, Chandan Anand, and Prasad Krishnan, decided to look at a very specific type of library: one organized like a graph. Imagine the servers (the librarians) are dots on a piece of paper, and the files (the books) are lines connecting them. If a file is stored on Server A and Server B, there is a line drawn between them. This "graph-based storage" is a common way to organize data in modern distributed systems.

In the past, researchers figured out how to retrieve files from these graph-libraries without any leakage. But the authors wondered: Can we do better if we relax the rules just a little? They proposed a new protocol they call G-WPIR (Graph-based Weak Private Information Retrieval).

Here is the core idea, explained with a simple analogy:

Imagine you are playing a game of "Guess the Secret" with a group of friends (the servers). In the old, strict version of the game, you had to flip a perfectly fair coin for every single friend to decide whether to ask them a question. If the coin landed heads, you asked; if tails, you stayed silent. This ensured no one could guess your secret, but it meant you had to talk to almost everyone, which took a long time.

The authors' new trick is to use a biased coin. Instead of a fair coin (50/50), they use a coin that is slightly weighted to land on "tails" (silence) more often.

The Trade-off: Because you stay silent more often, you talk to fewer friends, and you get your answer much faster. This is the "Rate" (speed).
The Cost: However, because you are silent more often, the friends who do hear you ask a question can make a slightly better guess about what your secret is. This is the "Leakage."

The paper proves that by adjusting how "heavy" the coin is (a parameter they call $p$ ), you can smoothly slide along a curve. You can choose to be almost perfectly private (coin is fair, speed is slow) or almost perfectly fast (coin is very heavy, speed is high, but privacy is low). The beauty of their solution is that it works for any shape of graph, whether it's a messy web of connections or a neat, organized structure.

The Two Ways to Measure "Leaking"

To make sure they were measuring the "leak" correctly, the authors used two different rulers:

Mutual Information: This measures how much the friend's knowledge about your secret increases on average. It's like asking, "On average, how much more do they know about my secret now?"
Maximal Leakage: This is a stricter ruler. It asks, "What is the best guess a friend can make about my secret after hearing me?" It looks at the worst-case scenario.

The paper provides exact mathematical formulas for both of these rulers, showing exactly how much speed you gain for every tiny bit of privacy you lose.

Special Cases: The Perfect Circle and the Two Teams

The authors didn't just stop at messy, random graphs. They tested their idea on two very specific, highly organized types of graphs to see how the math played out in extreme cases:

The Complete Graph (The "Everyone Knows Everyone" Party): Imagine a graph where every server is connected to every other server. In this scenario, the authors found that if you use their biased coin method, the speed can go all the way up to 1 (meaning you download exactly the size of the file you want, with zero extra waste) if you are willing to let the privacy drop to zero. But, they also showed that even with a tiny bit of privacy, you can get much closer to that perfect speed than before.
- A Twist: In the standard version of their game, the "first" friend in the line never leaks anything, while the "last" friend leaks the most. This felt unfair. So, they invented a Cyclic-Shift Protocol. Imagine the friends are sitting in a circle, and before the game starts, you secretly spin the circle so everyone has an equal chance of being in any seat. This makes the leakage equal for everyone. No one is singled out as the "leaky" one; the risk is shared fairly across the whole group.
The Complete Bipartite Graph (The "Two Teams" Game): Imagine the servers are split into two teams, Team A and Team B. Files are only stored between a member of Team A and a member of Team B (no one within Team A shares a file).
- Here, the results were fascinating. The authors found that the entire Team A could remain perfectly private (zero leakage) while Team B took on the leakage. It's like having a shielded team that never gets questioned, while the other team does the heavy lifting of the privacy trade-off. This allows for a very efficient system where some servers stay completely safe while others handle the "risk" to boost the overall speed.

What They Found (and What They Didn't)

The main finding of this paper is that speed and privacy are not a rigid "all-or-nothing" switch. By using a simple probabilistic trick (the biased coin) and organizing the servers based on a "sequential independent set" (a fancy way of grouping servers that don't share files), you can design a system that lets you dial in exactly how much privacy you want and get the corresponding speed.

The paper does not claim to have solved the problem of "perfect" privacy with "perfect" speed. In fact, it explicitly argues that you cannot have both at the same time if you want to be faster than the old methods. It proves that to get higher speeds, you must accept some leakage.

The authors are very confident in their math. They didn't just simulate this on a computer; they provided mathematical proofs (Theorems 1, 2, 3, 4, and 5) that show exactly how the rate and leakage relate for any graph, and specifically for complete and bipartite graphs. They showed that their protocol is "correct" (you always get the right file) and calculated the exact "leakage" numbers.

Why This Matters

This work is like finding a new gear in a car. Before, you could only drive in "Park" (perfect privacy, very slow) or "Reverse" (fast, but you crash into your privacy). This paper introduces a whole new set of gears in between. It shows system designers that they don't have to choose between being safe and being fast. They can choose a "sweet spot" where they are mostly safe but significantly faster.

The authors conclude by pointing out that while they have mapped out this new territory, there are still uncharted lands. They suggest that future work could look at what happens if the servers start talking to each other (colluding) or if the graphs get even more complex. But for now, they have successfully opened the door to a more flexible, efficient, and tunable way of keeping our digital secrets safe.

Technical Summary: Weak Private Information Retrieval for Graph-based Storage

Problem Statement

This work addresses the problem of Private Information Retrieval (PIR) in distributed storage systems modeled as graphs. In this Graph-based Storage (G-PIR) model, servers are represented as vertices of a graph $G=(V, E)$ , and files are represented as edges, where each file is stored jointly on the two servers corresponding to the edge's endpoints.

The standard objective in G-PIR is to maximize the rate (the ratio of the desired file size to the total expected download) while ensuring perfect information-theoretic privacy, meaning no server learns any information about the index of the file the client wishes to retrieve. However, perfect privacy often necessitates downloading significant amounts of redundant data, limiting the achievable rate.

This paper investigates Weak Private Information Retrieval (G-WPIR), a relaxation of the privacy constraint. In G-WPIR, servers are permitted to learn a bounded, non-zero amount of information about the desired file index. The goal is to design protocols that achieve higher retrieval rates by trading off a controlled amount of privacy leakage. The study focuses on two specific leakage metrics:

Mutual Information (MI) Leakage: $I(\theta; Q_n, A_n)$ , measuring the information the query-response pair reveals about the file index $\theta$ .
Maximal Leakage: $\log \sum_{q} \max_{m} P(Q_n=q|\theta=m)$ , measuring the worst-case multiplicative increase in the probability of guessing the file index.

Methodology

The authors propose a new G-WPIR scheme for arbitrary graphs, which serves as a probabilistic extension of a strictly private protocol previously established in [13]. The core methodology involves the following steps:

Sequential Independent-Set Partition: The vertex set $V$ is partitioned into $\kappa$ disjoint independent sets $I_1, I_2, \dots, I_\kappa$ using a sequential greedy algorithm. For any server $n$ , edges are classified as downstream (connecting to vertices in later sets $I_{s+1} \dots I_\kappa$ ) or upstream (connecting to vertices in earlier sets $I_1 \dots I_{s-1}$ ).
Biased Probabilistic Query Generation:
- The client generates queries using a biased coin toss with parameter $p \in [1/2, 1]$ .
- Downstream queries: For servers in $I_1$ and the downstream components of servers in $I_s$ ( $s \ge 2$ ), the client generates a query bit of '1' with probability $1-p$ and '0' with probability $p$ . A '0' query results in no response (null query), reducing the expected download.
- Upstream queries: For the upstream components of servers in $I_s$ ( $s \ge 2$ ), the query bits are constructed based on the queries generated by the upstream servers and the desired file index $\theta$ . Specifically, if the upstream server's query bit for a shared file is $X_j$ , the current server sets its bit to $X_j \oplus \mathbb{1}[\theta = \text{file}_j]$ . This ensures correctness (the file can be recovered via XORing responses) while introducing a dependency between the query and $\theta$ that causes leakage.
Trade-off Control: The bias parameter $p$ $p$ acts as a control knob.
- At $p = 1/2$ (fair coin), the protocol reduces to the strictly private scheme of [13] with zero leakage.
- As $p \to 1$ , null queries become more probable, significantly reducing the expected download (increasing the rate) but increasing the information leakage about $\theta$ .

Key Contributions

The paper initiates the formal study of G-WPIR and provides the following contributions:

General G-WPIR Scheme: A protocol for arbitrary graphs that achieves a smooth trade-off between rate and privacy under both MI and maximal leakage metrics.
Rate-Privacy Characterization: Theoretical derivation of the achievable rate and leakage bounds for any graph $G$ $G$ with $N$ $N$ vertices and independence number $\alpha(G)$ $α (G)$ .
- Theorem 1: Establishes the per-server MI leakage and the achievable rate $R(p)$ as a function of the bias $p$ and the graph's independent set decomposition.
- Theorem 2: Establishes the per-server maximal leakage and the same achievable rate $R(p)$ .
Special Graph Classes: The authors extend and refine the general protocol for two specific graph families:
- Complete Graphs ( $K_N$ ): They derive explicit rate-leakage trade-offs. Furthermore, they propose a Cyclic-Shift Biased Protocol that randomizes the vertex ordering before query generation. This modification equalizes the leakage across all servers, addressing the asymmetry inherent in the sequential partitioning of the general scheme.
- Complete Bipartite Graphs ( $K_{N_1, N_2}$ ): They analyze the protocol on bipartite graphs, showing that servers on one partition (Side A) incur zero leakage, while servers on the other partition (Side B) incur leakage proportional to the size of the first partition.

Key Results

Rate Improvement: By relaxing privacy, the protocol achieves rates strictly higher than the strictly private case. For a complete graph $K_N$ , the rate improves from $1/(N-1)$ (at $p=1/2$ ) to $1$ (at $p=1$ ).
Leakage Behavior:
- Leakage is zero for servers in the first independent set $I_1$ .
- For other servers, leakage increases with the number of upstream edges ( $U_n$ ) and the bias parameter $p$ .
- Under the cyclic-shift protocol for complete graphs, the worst-case leakage is reduced compared to the sequential protocol, providing a more uniform privacy profile.
Subpacketization: The proposed schemes operate with minimal subpacketization ( $L=1$ ), meaning files do not need to be subdivided into smaller blocks for the protocol to function, which is a significant practical advantage.

Significance and Claims

The paper claims to be the first formal study of Weak PIR (WPIR) specifically for graph-based storage systems. While WPIR has been studied in other distributed storage models (e.g., replicated or MDS-coded servers), this work extends the concept to the graph replication model where files are stored on pairs of servers.

The authors position their work as an extension of prior G-PIR results [6]–[13], demonstrating that relaxing the strict privacy constraint allows for the design of protocols with higher efficiency (rate) while maintaining a quantifiable and bounded level of privacy. The work provides the foundational rate-privacy trade-off curves for general graphs and specific topologies, establishing a baseline for future research.

The paper concludes by noting that several directions remain open, including:

Deriving information-theoretic converse bounds (upper limits) for WPIR on graphs.
Designing improved schemes for specific graph classes.
Investigating PIR in the presence of colluding servers within the graph-based storage model.