Weak Private Information Retrieval for Graph-based Storage
arXiv:2607.21014v1 [cs.IT] 23 Jul 2026
Shodasakshari Vidya, Chandan Anand, Prasad Krishnan
Abstract—A distributed storage system with graph-based replication consists of a collection of databases and the files they contain. The databases (or servers) are represented as the vertices of a graph, while each file is stored in a distinct pair of servers and is represented by an edge of this graph. Private information retrieval (G-PIR) on such a graph-based storage system involves a client which seeks to retrieve a desired file via a query-response protocol, without leaking the identity of the desired file index to any database. The goal of G-PIR is to maximize the rate (reciprocal of the total normalized download) under the privacy constraint. Prior work on GPIR has involved perfect information-theoretic privacy (i.e., null leakage). However, if the privacy constraint is relaxed, then PIR protocols could be designed that have even higher rates. We term such protocols as Graph-based Weak Private Information Retrieval (G-WPIR) protocols and initiate their formal study in this work. We propose a G-WPIR scheme for arbitrary graphs, and identify the trade-offs it achieves between rate and privacy, under two well known leakage metrics: mutual information leakage and maximal leakage. Our protocol employs minimal subpacketization (representing a file-size constraint) and employs a simple probabilistic query realization to obtain the smooth trade-off. We extend this protocol with some modifications to two special classes of graphs, the complete graphs and the complete bipartite graphs, and identify the corresponding rate-privacy trade-offs achieved.
I. I NTRODUCTION In Private Information Retrieval (PIR), a client desires to download a file from a set of distributed servers while keeping the identity of the desired file private from each server. To retrieve the client’s desired file privately, the client uses a query-response protocol, which ensures such private retrieval is called a PIR protocol. A PIR protocol downloads extra file bits to mask the desired file bits, thus achieving the desired privacy. The efficiency of a PIR protocol is measured using its rate, which is the ratio of the size of the desired file to the total number of downloaded bits in the protocol. For a given system model, the capacity of PIR is the supremum of the rate over all PIR protocols. A large body of work exists on PIR, with a considerable focus in the last several years in the information-theoretic privacy setting, starting from the seminal work by Sun and Jafar for non-colluding and colluding replicated databases [1], [2], including coded storage [3], and low subpacketization (or file-size) schemes [4], [5]. Shodasakshari, Chandan, and Dr. Krishnan are with the Signal Processing and Communications Research Center, International Institute of Information Technology, Hyderabad, 500032, India (email: {shodasakshari.vidya@research., chandan.anand@research., prasad.krishnan@}iiit.ac.in).
Any distributed storage can be modeled as (hyper)graphbased storage, where the servers are represented as vertices and files stored across any two or more servers are represented as edges or hyperedges, respectively. PIR for such graph-based storage (which we term as G-PIR) was first studied in [6], in which achievable schemes as well as converse results were presented, thus establishing lower and upper bounds on the capacity of G-PIR for graph replication colluding and noncolluding setups. G-PIR for storage based on simple graphs (where each file is stored on a distinct set of two servers, and no two servers share more than a single file) was further enhanced in [7]–[10]. In particular, these works presented results for G-PIR on various special classes of graphs such as star graphs, bipartite graphs, path graphs, and complete graphs. Any protocol for the complete graph KN on N vertices can be extended to a protocol for an arbitrary N -vertex graph, and thus the lower bounds for KN generalize to all graphs. Further extensions include G-PIR for multi-graph-based storage [11] in which two servers can share more than a single file, as well as symmetric G-PIR schemes [12]. Recently, a new class of G-PIR schemes for general graphs and star-graphs was introduced in [13]. The G-PIR scheme for general graphs presented in that work [13, Section IV] employs a probabilistic query generation protocol, requiring minimal subpacketization L = 1 (number of parts that the files must be subdivided into, for protocol execution). The setup of the protocol requires a pre-processing step, which is a decomposition of the storage graph into independent sets. For a graph with independence number α(G), this protocol achieves a rate lower bounded by 1/(N − α(G)/2) for any graph G with N vertices (databases) and independence number α(G), and exactly 1/(N −1) for the complete graph KN . This protocol achieves the best-known rate for balanced bipartite graphs, while higher-rate protocols are known [8] for complete graphs. Relaxing the perfect privacy constraint in PIR may enable achieving larger rates, albeit with some information leakage at the servers. Such schemes are termed weak-PIR (WPIR) schemes. The study of WPIR was initiated in multiple lines of work [14]–[16]. In these and subsequent works, various leakage metrics were used to measure the privacy leakage about the desired file index, including: mutual information leakage [14], maximal leakage [17], worst-case information leakage [18], differential privacy [16], and converse induced privacy metric [19]. These leakage measures have previously been adopted in various WPIR settings, such as colluding-
free replicated servers [20], [21], MDS-coded storage servers [20]–[22], and colluding servers [20], [21]. In this work, we propose a new WPIR scheme for graphbased storage, adopting both mutual information leakage and maximal leakage as our privacy metrics. The contributions of this work are as follows: • Section II contains preliminaries, system model, and GWPIR basics. Subsection II-C contains the statements of the main results of this work. Theorem 1 describes the rateprivacy tradeoff for arbitrary graphs, with respect to the mutual information leakage metric. Theorem 2 gives the rate-privacy tradeoffs under the maximal leakage metric. • In Section III, we present our G-WPIR scheme, which achieves the rate-privacy tradeoffs mentioned in Theorems 1 and 2. This protocol is a natural weaker version of the general graph-PIR scheme proposed in [13, Section IV]. We show the Theorems 1 and 2 by obtaining the rate achieved by this protocol, and the corresponding leakage metrics. • In Section V, we consider two special classes of graphs: complete and complete bipartite graphs. We construct GWPIR schemes for these, using the protocol in Section III and its refinements. We show the corresponding rate-privacy tradeoffs for these graphs. In summary, this work initiates the formal study of WPIR for graph-based storage, extending results in prior work for WPIR in other models of distributed storage [14], [20], [23]. We end the paper in Section VI with directions for further work. Notation: Let N be a positive integer then [N ] denotes {1, 2, · · · , N }. Consider I ⊂ [N ] and a set a = (a1 , a2 , · · · , an ) then we define aI = {ai : i ∈ I}. For disjoint sets A and B, their disjoint union is denoted as A ⊔ B. The symbols 0 and 1 denote all-zero and all-one vectors over F2 of appropriate lengths, understood from the context. For q ∈ Fn2 , let w(q) denote its Hamming weight. The symbol ⊕ denotes the logical XOR operator. A biased coin toss is modeled by a Bernoulli random variable X ∼ Bern(p), where P (X = 1) = 1 − P (X = 0) = p. The case p = 1/2 corresponds to a fair coin. Let log denote the base-2 logarithm. The binary entropy function is denoted by Hb (p) = −p log(p)−(1−p) log(1−p). For a random variable X, E[X] denotes expectation with respect to its underlying distribution of X. An (undirected) graph G is composed of vertices V and edges E. An independent set of a graph is a collection of vertices, no two of which share an edge. The size of the largest independent set of a graph is termed its independence number, denoted by α(G). II. S YSTEM MODEL AND M AIN R ESULTS A. System Model 1) Storage Model: We consider a distributed storage system consisting of N servers, indexed by the vertex set V = [N ] ≜ {1, 2, . . . , N } of a simple, undirected graph G = (V, E). The edge set E defines the replication structure, where each edge {i, j} ∈ E represents a distinct file Wi,j stored jointly on servers i and j. Server n stores all files {Wn,m : {n, m} ∈
E}, which we also write as Wn1 , Wn2 , . . . , Wndn , where dn = |{m : {n, m} ∈ E}| denotes the degree of vertex n. We denote the total number of files by K = |E|. All files are assumed to be independent and uniformly distributed, each of entropy H(Wi,j ) = L bits, where L ≥ 1 denotes the subpacketization of the scheme. Throughout this work, we restrict attention to the unit-subpacketization setting, i.e., L = 1. 2) PIR Protocol: A client wishes to privately retrieve a target file Wθ , where the file index θ is drawn uniformly at random from the edge set E. The client communicates with the servers via a query-response protocol: it sends a query Qn to each server n ∈ V, and receives a corresponding response An . The query Qn is a function of θ and private client-side randomness, independent of the stored files. The query to server n takes the form of a binary vector Qn = (f1n , f2n , . . . , fdnn ) ∈ Fd2n . Upon receiving a non-zero query, server n returns the linear combination An =
dn M
fjn Wnj ,
(1)
j=1
where ⊕ denotes addition over F2 . The query Qn = 0 is interpreted as a null query, eliciting no response. A PIR protocol must recover the client’s desired file Wθ from the received responses, i.e., (2) H Wθ | Q[N ] , A[N ] = 0. The rate of a variable-download PIR protocol is defined as R ≜
L , E[D]
(3)
where L = 1 is the subpacketization and E[D] = P H(A n | Qn ) is the expected total download. The n∈V capacity C(G) is the supremum of R over all correct PIR protocols. B. Strict and Weak Privacy The classical (strict, or information-theoretically perfect) privacy requirement in PIR demands that no individual server learns any information about the desired file index θ from its query-response pair: I(θ; Qn , An ) = 0,
∀ n ∈ V.
(4)
Information-theoretic perfect PIR protocols for graph-based storage were initiated in [6] and further developed for various general and specific graph classes in a sequence of works [7]– [10]. In this work, we study weak (or ε-private) PIR protocols, in which each server is permitted to learn a bounded but nonzero amount of information about θ. We adopt two leakage metrics to quantify this. Definition 1 (Per-server Mutual Information Leakage). The mutual information (MI) leakage at server n is defined as εMI ≜ I(θ; Qn , An ) . (5) n A protocol is ε-MI-private if εMI n ≤ ε for all n ∈ V.
Definition 2 (Per-server Maximal Leakage). The maximal leakage [17] at server n is defined as X εmax max PQn |θ (qn | m), (6) ≜ log n qn ∈Qn
m∈[K]
where the sum ranges over all realizations qn of Qn . A protocol is ε-maximally-private if εmax ≤ ε for all n ∈ V. n These leakage measures have been adopted in various WPIR settings before, such as non-colluding and replicated servers [21], [24], [25], for MDS-coded storage servers [21], [22] and colluding servers [21]. In this work, we adopt these metrics to present new protocols for PIR with graph-based storage. C. Main Results In this subsection, we present the main results of this work, which new G-WPIR achievable rate-privacy tradeoffs with respect to the mutual information and maximal leakage metrics, for arbitrary graph-based storage. The new scheme which achieves these tradeoffs is a natural extension of the scheme for complete graphs available in [13][Section IV]. Towards explaining our protocol, we first explain the preprocessing step used in [13] that obtains a partition of the graph into independent sets. 1) Preliminaries: Following [13], our protocols rely on a partition of the vertex set V into Fκ disjoint independent κ sets I1 , I2 , . . . , Iκ , satisfying V = s=1 Is . This partition is constructed sequentially: for each s ∈ [κ], the set Is is taken as a largest independent set of the induced subgraph G[Is ∪· · ·∪Iκ ]. We refer to this as the sequential independentset partition1 of G. For a server n ∈ Is , the edges incident on n are classified according to the partition. The downstream degree d↓n of vertex n is the number of edges connecting n to a vertex in Is+1 ∪ · · · ∪ Iκ , while the upstream degree d↑n = dn − d↓n is the number of edges connecting n to a vertex in I1 ∪ · · · ∪ Is−1 . / I1 , since otherwise n could have Note that d↑n ≥ 1 for all n ∈ been absorbed into an earlier independent set, contradicting its maximality. For each upstream edge ej incident on server n, we write ej ∈ E for the corresponding file index, where j ∈ [d↑n ]. Accordingly, the query vector Qn is decomposed as Qn = Q↓n , Q↑n , (7) d↓
where Q↓n ∈ F2n contains the weights for downstream edges d↑ and Q↑n ∈ F2n contains the weights for upstream edges. For servers in I1 , the upstream subvector is non-existent, and Qn consists entirely of Q↓n . 1 The execution of the protocol does not depend on the assumption of I s being the largest independent set at that stage. It is sufficient to consider maximal independent sets at each step instead. We can construct such a decomposition in polynomial time via a greedy algorithm. The rate achieved will depend on the size of these independent sets; specifically, the quantity α(G) appearing in (10) and (19) below is |I1 | in general, and equals α(G) precisely when I1 is chosen as a largest independent set of G, as in the sequential construction above.
2) Leakage-Rate Tradeoffs: The proofs of the following theorems are given in Section III. Theorem 1 (MI Leakage and Rate Tradeoff).FAccording κ to the independent-set decomposition V = s=1 Is , the per-server MI leakage satisfies ( 0, n ∈ I1 , MI εn = (8) ↑ H Qn − Un · Hb (p), n ∈ Is , s ≥ 2, where X P Q↑n = q log P Q↑n = q , H Q↑n = −
(9)
n q∈FU 2
with the marginal P (Q↑n = q) given by (22)–(25). For servers in Iκ , the formula holds with Un = dn (since d↓n = 0). Also, the biased protocol with parameter p ∈ [1/2, 1] achieves rate R(p) ≜ 1/E[D(p)], where the expected download is E[D(p)] = |I1 | · (1 − p) κ−1 X X Un (2p − 1) pUn +1 + 1− K− K p s=2 n∈Is U X p n Un (2p − 1) + 1− K− . (10) K p n∈Iκ
This expression holds for any sequential independent-set partition satisfying the degree properties of Subsection II-C1, whether each Is is chosen as a largest or merely a maximal independent set (Footnote 1). Under the primary construction, in which I1 is itself a largest independent set of G, |I1 | = α(G), recovering the form used in the remainder of the paper. Theorem 2 (Maximal Leakage and Rate Tradeoff). The biased protocol with parameter p ∈ [1/2, 1] achieves the same rate R(p) as given by (10). According to the independent-set decomposition, the per-server maximal leakage satisfies n ∈ I1 , 0, max U εn = (11) p + p n (1 − 2p) log , n∈ / I1 . 1−p III. A W EAK PIR S CHEME FOR G ENERAL G RAPHS We now present a weak PIR protocol for general graphs. Our protocol is an extension of the protocol from [13] which achieves perfect information-theoretic privacy. A. A G-WPIR Scheme for arbitrary graph The strictly private protocol of [13] generates queries sequentially over the independent sets, and our G-WPIR scheme here follows the same. We summarize Each server n ∈ I1 is assigned a binary query Qn ∈ {0, 1} according to a Bern(p) distribution. For n ∈ Is , s ≥ 2, the downstream subvector Q↓n is drawn from {0, 1} via an independent Bern(p) coin, while each upstream bit is set according to a rule that involves the corresponding upstream bit and the desired file index. Choosing the value of p allows for a smooth trade-off between
the rate and the privacy, thus resulting in Theorems 1 and 2. Fixing p = 0.5 recovers the protocol in [13][Section IV], which is strictly private. An example of the execution of the protocol is available in [13][Example 2] for the p = 0.5 case. This example also illustrates the execution of our WPIR protocol here, except that in our case p is any value in [0.5, 1]. We now present the complete design of the protocol. Let G = (V, E) be the storage graph on N vertices and K = |E| files, with sequential independent-set partition V = I1 ⊔ I2 ⊔ · · · ⊔ Iκ as defined in Subsection II-C1. Let θ ∈ E denote the desired file index, drawn uniformly from E, and fix a bias parameter p ∈ [1/2, 1]. The client generates a binary query vector Qn ∈ Fd2n for each server n ∈ V by the following sequential procedure. Step 1 – Queries for I1 . Every server n ∈ I1 has no upstream edges (d↑n = 0), so all incident edges are downstream (d↓n = dn ). For each n ∈ I1 , the client draws an independent coin Cn with P (Cn = 0) = p and P (Cn = 1) = 1 − p, and sets ( 1 ∈ Fd2n , with probability 1 − p, Qn = (12) 0 ∈ Fd2n , with probability p. Step s – Queries for Is , s ∈ {2, . . . , κ}. For each n ∈ Is , let Un ≜ d↑n = dn − d↓n denote the number of upstream edges, and let Un = {e1 , e2 , . . . , eUn } ⊆ E be the collection of upstream edges (equivalently, the file indices) at server n. For each j ∈ [Un ], the file ej is shared with some upstream server mj ∈ It , t < s. Let Xj ≜ Cmj be the coin drawn for mj in Step t; since ej is a downstream edge of mj , the value Xj is precisely the query bit that mj assigned to the shared file Wej . The variables X1 , . . . , XUn are mutually independent with P (Xj = 0) = p and P (Xj = 1) = 1 − p for all j. The query Qn = (Q↓n , Q↑n ) is constructed as follows. 1) Downstream subvector Q↓n : If d↓n > 0, the client draws a fresh coin Cn with P (Cn = 0) = p and P (Cn = 1) = 1 − p, independent of all prior randomness and of θ, and sets 1 ∈ Fd↓n , with probability 1 − p, 2 ↓ Qn = (13) 0 ∈ Fd↓n , with probability p. 2
If d↓n
= 0 (i.e., n ∈ Iκ ), the downstream subvector is absent. 2) Upstream subvector Q↑n : The j-th component of Q↑n , corresponding to the upstream file ej ∈ Un , is set to fjn = Xj ⊕ 1[θ = ej ],
j ∈ [Un ].
(14)
That is, fjn = Xj when ej ̸= θ (the indicator is zero, bits pass unmodified), and fjn = Xj ⊕ 1 when ej = θ (the indicator is one, the bit is flipped). Ldn n j Server responses. Server n returns An = j=1 fj Wn if Qn ̸= 0, and sends no response if Q = 0. The client recovers n L the desired file as Wθ = n∈V An . Remark 1. At p = 1/2 all coins are fair, every query bit is Bern(1/2) independently of θ, and the protocol coincides
with the strictly private scheme of [13]. The central idea of the present work is to replace the fair coin with a biased one parametrized by p ∈ [1/2, 1]. Setting p > 1/2 makes null queries become more probable, reducing the expected download and raising the rate at the cost of nonzero leakage at every server with at least one upstream edge. The bias parameter p thus controls the leakage-rate tradeoff, as indicated by Theorems 1 and 2. At p = 1, every coin is 0 almost surely, so Xj = 0 for all j and rule (14) reduces to fjn = 1[θ = ej ], thus completely revealing θ to the downstream server storing Wθ . □ Proposition 1 (Correctness). The L A = Wθ . n n∈V
protocol
satisfies
Proof. We repeat the arguments in [13] for completeness. Consider a file Wm,n , which is the ith file at upstream server m and the j th file at the downstream server n. Suppose Wm,n ̸= Wθ , then by the query construction fim = fjn . m n However, if Wm,n L= Wθ , then fi = fj ⊕ 1. Thus, the sum of all responses n An = Wθ . This completes the proof. IV. C OMPLETING T HE P ROOFS OF T HEOREMS 1 AND 2 This section establishes the three components needed to prove Theorems 1 and 2. Section IV-A derives the expected download E[D(p)] (10), which gives the achievable rate R(p) common to both theorems. Section IV-B computes the perserver MI leakage, establishing (8) of Theorem 1. Section IV-C computes the per-server maximal leakage, establishing (11) of Theorem 2. A. Rate PWith L = 1, the rate is R = 1/E[D] where E[D] = n∈V P (Qn ̸= 0), as the download from each server is 1 bit. Servers in I1 . From (12), P (Qn = 0) = p, so P (Qn ̸= 0) = 1 − p. Servers in Is , s ≥ 2. Since Q↓n ⊥ Q↑n , the null-query event {Qn = 0} requires both subvectors to be zero. We first compute P (Q↑n = 0) by conditioning on θ: K 1 X P Q↑n = 0 | θ = t . P Q↑n = 0 = K t=1
(15)
Recall that each upstream vertex of vertex n has precisely one file shared with n. Hence, for the K − Un indices t ∈ / Un , all bits in Q↑n are distributed as Bern(1 − p). Further, note that all upstream vertices at n use independent coin flips to generate their respective downstream query subvectors. Thus, we have P (Q↑n = 0 | θ = t) = pUn . For each of the Un indices t = ek ∈ Un , bit k follows Bern(p) while the other Un −1 bits follow Bern(1−p), so P (Q↑n = 0 | θ = ek ) = (1−p)·pUn −1 . Substituting into (15): 1 (K − Un ) pUn + Un (1 − p) pUn −1 P Q↑n = 0 = K pUn −1 = [Kp + Un (1 − 2p)] . (16) K
For n ∈ Is with d↓n > 0 (s ∈ [2 : κ − 1]), multiplying by P (Q↓n = 0) = p, we have pUn +1 Un (2p − 1) P (Qn = 0) = K− . (17) K p For n ∈ Iκ (d↓n = 0), the full query equals the upstream subvector: Un (2p − 1) pUn K− . (18) P (Qn = 0) = K p Since (2p − 1)/p ∈ [0, 1] for p ∈ [1/2, 1] and Un ≤ K, the term (K − Un (2p − 1)/p) is non-negative. Hence the nullquery probabilities in (17) and (18) are non-negative, and from (10) we have the following corollary. Corollary 1 (Rate lower bound). Therefore, 1 1 , . R(p) ≥ max N − |I1 | · p N − 1
(19)
Under the primary (largest-independent-set) construction, |I1 | = α(G) and (19) reads R(p) ≥ max{1/(N − α(G)p), 1/(N − 1)}; setting p = 1/2 recovers R ≥ 2/(2N − α(G)) from [13]. Since |I1 | ≤ α(G) for any merely maximal choice of I1 , and (19) is increasing in |I1 |, the largestindependent-set construction gives the best rate guarantee attainable from this bound; a greedy maximal-only choice can only weaken it, consistent with Footnote 1. For the complete graph KN , every independent set is a singleton, so |I1 | = α(KN ) = 1 regardless of which vertex is chosen, and E[D(p)] = N − 1 up to correction terms, giving R(p) ≈ 1/(N − 1). This establishes (10) and the rate R(p) = 1/E[D(p)] claimed in both Theorems 1 and 2. B. Mutual Information (MI) Leakage We now derive the per-server MI leakage, deriving (8) of Theorem 1. Since An is a deterministic function of Qn and the stored files, and the files are independent of θ, we have I(θ; Qn , An ) = I(θ; Qn ). We now find I(θ; Qn ) at each server n. Servers in I1 . As Qn ⊥ θ for every n ∈ I1 by query design, we have I(θ; Qn ) = 0. Servers in Is , s ≥ 2. Since Q↓n is generated by the independent coin Cn , we have Q↓n ⊥ θ and Q↓n ⊥ Q↑n . By the chain rule of mutual information, I(θ; Qn ) = I(θ; Q↓n ) + I(θ; Q↑n | Q↓n ) = I(θ; Q↑n ),
(20)
so the entire leakage is carried by the upstream subvector. We compute I(θ; Q↑n ) = H(Q↑n ) − H(Q↑n | θ). Conditional entropy H(Q↑n | θ). From (14), bit j is fjn = Xj ⊕ 1[ej = θ]. The coins X1 , . . . , XUn are mutually independent with P (Xj = 0) = p. Case A (θ ∈ / Un ): The indicator is zero for all j, so fjn = Xj ∼ Bern(p) for all j. The bits are i.i.d., giving H(Q↑n | θ) = Un · Hb (p).
Case B (θ = ek for some k ∈ [Un ]): Only bit k is flipped: fkn = Xk ⊕ 1 ∼ Bern(1 − p), while fjn = Xj ∼ Bern(p) for all j ̸= k. Since Hb (p) = Hb (1 − p), and all Un bits remain jointly independent, thus H(Q↑n | θ = ek ) = Un · Hb (p). In both cases H(Q↑n | θ) = Un · Hb (p), and averaging over θ confirms H Q↑n | θ = Un · Hb (p). (21) Marginal distribution of Q↑n . We compute P (Q↑n = q) for n each q ∈ FU by the law of total probability. Define the no2 hit conditional distribution P0 (q) ≜ P Q↑n = q | θ ∈ / Un = pUn −w(q) (1 − p)w(q) , (22) and for each k ∈ [Un ] the hit-at-k conditional distribution Pk (q) ≜ P Q↑n = q | θ = ek = pUn −w(q⊕ek ) (1−p)w(q⊕ek ) , (23) n where ek ∈ FU is the standard basis vector with 1 at position 2 k, reflecting the flip of bit k in (14). Noting that ( w(q) − 1, qk = 1, w(q ⊕ ek ) = (24) w(q) + 1, qk = 0, and using P (θ ∈ / Un ) = (K − Un )/K and P (θ = ek ) = 1/K, the marginal distribution of Q↑n is U
P Q↑n = q
=
n 1 X K − Un Pk (q). P0 (q) + K K
(25)
k=1
Combining (20) and (21): I(θ; Qn ) = H(Q↑n ) − Un · Hb (p), with H(Q↑n ) computed from the marginal (25) via (9). Remark 2. At p = 1/2, both P0 (q) = 2−Un and Pk (q) = 2−Un for all q and k, so the marginal (25) is the uniform MI ↑ n = distribution on FU 2 , giving H(Qn ) = Un bits and εn Un − Un = 0, confirming strict privacy. Note that the MI leakage is zero at servers in I1 . □ Combined with the rate result of Section IV-A, this completes the proof of Theorem 1. C. Maximal Leakage We next derive the per-server maximal leakage, establishing (11) of Theorem 2. Recall that P the maximal leakage at server n is defined as εmax = log q∈Qn maxm∈[K] PQn |θ (q | n m) [17]. Operationally, for each possible observed query q, the server identifies the single file index m that maximises the probability of having generated q; these maximal probabilities are then summed over all possible queries and the logarithm is taken. We now compute the maximal leakages for the biased protocol. Servers IN I1 : Since Qn ⊥ θ for every n ∈ I1 , we PQn (q) for each q, so P have maxθ PQn |θ (q | θ) = max max P (q | θ) = 1 and ε = log 1 = 0. θ Qn |θ n q ↓ ↑ Servers in Is , s ≥ 2: Let q = (q , q ) denote a query sample at server n, with the upstream and downstream sub-queries q ↑ and q ↓ respectively. denote the Q↓n is independent of θ and the
full query factorises as PQn |θ (q | m) = PQ↓n (q ↓ ) · PQ↑n |θ (q ↑ | d↓ F2n
m), summing PQ↓n (q ↓ ) over all q ↓ ∈ gives 1. The downstream subvector therefore vanishes from the maximal leakage sum, giving X εmax = log max P Q↑n = q ↑ | θ = m . (26) n n q ↑ ∈FU 2
m∈[K]
We identify the maximising m for each q ↑ by expressing Pk (q ↑ ) as a scalar multiple of P0 (q ↑ ). From (22) and (23), when θ = ek ∈ Un only the k-th bit is flipped, so ↑
↑
pUn −w(q ⊕ek ) (1 − p)w(q ⊕ek ) Pk (q ↑ ) = P0 (q ↑ ) pUn −w(q↑ ) (1 − p)w(q↑ ) p , qk↑ = 1, 1−p = 1−p , qk↑ = 0, p
(27)
using (24). Since p ∈ [1/2, 1) implies p/(1 − p) ≥ 1 while (1−p)/p ≤ 1, the ratio in (27) exceeds 1 if and only if qk↑ = 1. We now determine the maximising m case by case. Case I: w(q ↑ ) = 0. All bits of q ↑ are 0, so for every k ∈ [Un ] the ratio Pk (q ↑ )/P0 (q ↑ ) = (1 − p)/p ≤ 1. No upstream hypothesis θ = ek can exceed P0 (q ↑ ), so θ ∈ / Un is the maximiser: max P Q↑n = q ↑ | θ = m = P0 (0) = pUn . (28) m
Case II: w(q ↑ ) ≥ 1. There exists at least one position k with qk↑ = 1. For such k, the ratio Pk (q ↑ )/P0 (q ↑ ) = p/(1 − p) ≥ 1, strictly exceeding 1 for p > 1/2. The server can therefore select any such k as the maximising hypothesis, giving p max P Q↑n = q ↑ | θ = m = · P0 (q ↑ ). (29) m 1−p Summing over all 2Un possible query vectors and grouping by Hamming weight: X max P Q↑n = q ↑ | θ = m n q ↑ ∈FU 2
m
= pUn +
Un Un −w p X Un p (1 − p)w . 1 − p w=1 w
(30)
PUn Un Un −w By the binomial theorem, w=0 (1 − p)w = (p + w p P U U n Un −w n 1 − p)Un = 1, so (1 − p)w = 1 − pUn . w=1 w p Substituting into (30): X p 1 − pUn max P Q↑n = q ↑ | θ = m = pUn + m 1−p ↑ q
pUn (1 − p) + p − pUn +1 1−p p + pUn (1 − 2p) = . (31) 1−p =
Taking logarithms gives (11).
Remark 3. For fixed p ∈ (1/2, 1), the leakage is strictly increasing in Un : differentiating the numerator with respect to Un gives pUn ln(p)(1 − 2p) > 0 (since ln(p) < 0 and 1 − 2p < 0 for p ∈ (1/2, 1)), so a server with more upstream edges always incurs higher maximal leakage. The maximal leakage depends on the graph only through the upstream degree Un , and is also strictly increasing in p for fixed Un ≥ 1. □ Combined with the rate result of Section IV-A, this completes the proof of Theorem 2. V. S PECIAL G RAPHS We now specialize the general scheme of Section III and resulting theorems for two important graph families: complete graphs and complete bipartite graphs. For each family, the simplicity of the graph-structure allows the general leakage and rate expressions to be substantially simplified. The symmetry of complete graphs allows us to add a further randomization during query generation, which enables us to get uniform leakages at all servers. A. Complete Graphs Consider the complete graph KN on N vertices, in which every pairof servers shares a file. The total number of files is K = N2 = N (N − 1)/2, and the independence number is α(KN ) = 1, since no two vertices are non-adjacent. The sequential independent-set partition of Subsection II-C1 therefore consists of κ = N singleton sets, one vertex per set: Is = {vs } for each s ∈ [N ], where the vertices are labeled in the order they are selected. The server vs ∈ Is has total degree dn = N −1, of which d↓n = N −s edges point downstream (to servers in Is+1 , . . . , IN ) and d↑n = s−1 edges point upstream (to servers in I1 , . . . , Is−1 ). In particular, the server in I1 has no upstream edges (d↑n = 0), and the server in IN has no downstream edges (d↓n = 0). Theorem 3 (Leakage-Rate Tradeoff for KN ). The biased protocol on KN with parameter p ∈ [1/2, 1] satisfies: (i) MI leakage: For server vs , ↑ εMI (32) vs = H Qvs − (s − 1) Hb (p), where H(Q↑vs ) is computed from (22)–(25) with Un = s − 1 and K = N (N − 1)/2. The MI leakage is zero for s = 1 and for all servers at p = 1/2, and increases with p for each fixed s ≥ 2; the per-server variation with s is illustrated in Fig. 1. (ii) Maximal leakage: s = 1, 0, max εvs = p + ps−1 (1 − 2p) , s ∈ {2, . . . , N }. log 1−p (33) The leakage (33) is strictly increasing in s: servers encountered later accumulate more upstream edges and therefore leak more, with maximum leakage at IN . (iii) Rate: The expected download is E[DKN (p)] = (1 − p)
N −1 X
ps (s − 1)(2p − 1) K− K p s=2 N −1 p (N − 1)(2p − 1) + 1− K− , K p (34)
observes only its own query Qn , which is distributed according to the mixture
with K = N (N −1)/2, giving rate RKN (p) = 1/E[DKN (p)].
where Ps (Q = q | θ) is the query distribution of a server at position s under the original biased protocol.
+
1−
Proof. Parts (i) and (ii) follow by substituting Un = s − 1 into Theorems 1 and 2 respectively. Part (iii) follows by substituting |Is | = 1 and α(KN ) = 1 into (10). Remark 4. The expected download (34) satisfies E[DKN (1/2)] = N − 1 and E[DKN (1)] = 1, giving RKN (1/2) = 1/(N − 1) and RKN (1) = 1. At p = 1/2: (2p − 1) = 0, soPnull-probabilities reduce to (1/2)s and N −1 s (1/2)N −1 ; using = 1/2 − (1/2)N −1 gives s=2 (1/2) E[DKN (1/2)] = N − 1, recovering [13]. At p = 1: the non-null probability for server vs is (s − 1)/K, so PN −1 E[DKN (1)] = (1/K) s=1 s = 1. At p = 1/2 the protocol is strictly private and all N − 1 non-first servers respond. At p = 1 only the server whose upstream edge coincides with θ responds, giving D = 1 and R = 1 — the maximum rate at the cost of completely revealing θ. The rate RKN (p) is strictly increasing in p, ranging from 1/(N − 1) to 1. □ Remark 5. The boundary values have a natural interpretation. At p = 1/2, the protocol is strictly private and the download equals N − 1: essentially, all N − 1 servers other than the one in I1 (which is queried only half the time) respond. At p = 1, the biased coins are all identically zero, so only the server whose upstream edge coincides with the desired file θ receives a non-null query on average; precisely one server responds, giving D = 1 and R = 1. This represents the maximum rate achievable by the protocol family, at the cost of revealing θ entirely to a server which contains it. The rate RKN (p) is strictly increasing in p, ranging from 1/(N − 1) at p = 1/2 to 1 at p = 1. □
N
(35)
Theorem 4 (Protocol 2 Leakage-Rate Tradeoff). Under Protocol 2 with parameter p ∈ [1/2, 1), every server vn has the same marginal query distribution and hence identical leakage by any measure. The expected download satisfies E[Dshift ] = E[DKN (p)], where E[DKN (p)] is given by (34), while the common per-server leakage values εmax shift (maximal leakage) and εMI (MI leakage) satisfy: shift (i) Maximal leakage upper bound: ! N 1 X p + ps−1 (1 − 2p) max (36) εshift ≤ log N s=1 1−p p (1 − 2p)(1 − pN ) = log + . (37) 1−p N (1 − p)2 (ii) MI leakage upper bound: N N 1 X 1 X MI ε vs = H Q↑vs − (s − 1) Hb (p) . N s=2 N s=2 (38) Both bounds equal zero at p = 1/2, consistent with strict privacy.
εMI shift ≤
Proof. Identical marginal distributions and rate invariance. For any server vn , any query value q, and any file index θ, conditioning on the shift R: P (Qn = q | θ) =
N X
P (R = r) · P (Qn = q | θ, R = r)
r=1 N
B. Leakage-Averaged Protocol for KN via Cyclic Shift In the biased protocol of Section III-A, the leakage at server vs strictly increases with its partition index s: the server in I1 leaks nothing, while the server in IN incurs the maximum leakage. This asymmetry is purely an artefact of the ordering imposed by the sequential partition; the underlying graph KN treats all vertices identically. We now describe a modified protocol that equalises the per-server leakage across all servers by prepending a uniform random cyclic relabelling of the vertices before the query process, while leaving the expected download — and hence the rate — unchanged. Protocol 2 (Cyclic-Shift Biased Protocol). Before executing the biased protocol of Section III-A, the client draws a shift offset R uniformly and independently at random from [N ]. It relabels the vertices of KN by the cyclic permutation σR : vi 7→ v(i+R−2 mod N )+1 , and runs the biased protocol on the relabelled graph. The offset R is private client-side randomness, not revealed to any server. Server vn therefore
1 X Ps (Q = q | θ) , N s=1
P (Qn = q | θ) =
=
1 X P −1 (Q = q | θ). N r=1 σr (n)
(39)
Since σr is a cyclic permutation of [N ], as r ranges over [N ] the position σr−1 (n) P takes each value in [N ] exactly once. N Hence (39) equals N1 s=1 Ps (Q = q | θ), independent of n, giving every server the same marginal distribution and hence identical leakage. For the download, since each vn occupies position s with probability 1/N : E[Dshift ] =
N N X 1 X n=1
N s=1
Ps (Q ̸= 0) =
Ps (Q ̸= 0) = E[DKN (p)].
s=1
Part (i). Using maxθ N1 non-negative fs :
1 s fs (θ) ≤ N
P
N
εmax shift = log
N X
X q
max θ
P
s maxθ fs (θ) for
1 X Ps (q | θ) N s=1
Fig. 1: Rate and εMI vs (MI leakage) trade-offs for complete graph with 5 vertices (K5 ), at each server. The dotted line represents the tradeoff achieved at each server by the cyclicshift-based protocol in Subsection V-B.
N X 1 X ≤ log max Ps (q | θ) . N θ s=1 q | {z }
C. Complete Bipartite Graphs (40)
= exp(εmax vs )
s−1 (1−2p)]/(1−p) from (33) Substituting exp(εmax vs ) = [p+p PN s−1 gives (36). Evaluating the geometric sum (1 − s=1 p 2p) = (1 − 2p)(1 − pN )/(1 − p) and dividing by N (1 − p) gives (37). Part (ii). Since R ⊥ θ, the chain rule gives
εMI shift = I(θ; Qn ) ≤ I(θ; Qn , R) = I(θ; R) +I(θ; Qn | R) | {z } =
=0 N X
N 1 X MI 1 I(θ; Qvs ) = ε , N s=1 N s=2 vs
Fig. 2: Rate and εmax (maximal leakage) trade-offs for comvs plete graph with 5 vertices (K5 ). The dotted line represents the tradeoff achieved at each server by the cyclic-shift-based protocol in Subsection V-B.
(41)
where the last equality uses I(θ; Qv1 ) = 0. Remark 6. Both bounds are strictly smaller than the worstcase per-server leakage of Protocol 1. For the maximal leakP εmax 1 vs age, the bound (37) satisfies εmax ≤ log ≤ shift se N εmax , where the second inequality holds because the arithvN max metic mean of eεvs is at most its maximum. The actual perserver leakage of the mixture is strictly below the bound; for example, at N = 3 and p = 0.7, the exact mixture maximal leakage is 0.125, the bound (37) gives 0.307, and the worst-case leakage under Protocol 1 is εmax = 0.452. v3 These improvements are visible in Fig. 2, where the dotted line (Protocol 2) lies strictly below the solid curves (Protocol 1) for all p > 1/2. □
We now specialise our general protocol in Section III-A to the complete bipartite graph KN1 ,N2 , where side A has N1 vertices and side B has N2 vertices. Assume without loss of generality that N1 ≥ N2 . The total number of servers is N = N1 + N2 , the total number of files is K = N1 N2 , and the independence number is α(KN1 ,N2 ) = N1 . 1) Partition Structure: The sequential independent-set partition of Section III-A produces exactly κ = 2 sets: I1 = A (side A, N1 vertices) and I2 = B (side B, N2 vertices). Since KN1 ,N2 is bipartite, every edge crosses between the two sides, so all edges incident on n ∈ I1 are downstream and all edges incident on n ∈ I2 are upstream. Concretely: ↑ ↓ • Every server n ∈ I1 has dn = N2 , dn = 0, Un = 0. ↑ ↓ • Every server n ∈ I2 has dn = 0, dn = N1 , Un = N1 . In particular, all N1 servers on side A are structurally identical (zero upstream edges, and N2 downstream edges) and all N2 servers on side B are structurally identical (N1 upstream edges each, and no downstream edges), so the leakage and download contributions depend only on which side a server belongs to. 2) Leakage Expressions: Theorem 5 (Leakage-Rate Tradeoff for KN1 ,N2 ). The biased protocol on KN1 ,N2 with parameter p ∈ [1/2, 1] satisfies: (i) Side-A servers (n ∈ I1 ): Every side-A server has zero leakage, i.e., εMI = 0, n
εmax = 0. n
(42)
(ii) Side-B servers (n ∈ I2 ), all equal: For each side-B server n, we have the leakage metrics as follows p + pN1 (1 − 2p) max εn = log , (43) 1−p
εMI = H Q↑n − N1 Hb (p), n
(44)
where H(Q↑n ) is given by (9) and (25) with Un = N1 and K = N 1 N2 . (iii) Expected download and rate: E DKN1 ,N2 (p) = N1 (1−p) + N2 − pN1 −1 1+p(N2 −2) , (45) and rate R(p) = 1/E[DKN1 ,N2 (p)]. Proof. Part (i) follows directly from Theorems 1 and 2, since side-A servers lie in I1 , where both theorems assign zero leakage irrespective of Un . Part (ii) follows by substituting Un = N1 into Theorems 1 and 2, applied to side-B servers, which lie in I2 = Iκ . Equality of leakage across all side-B servers follows from their structural identity: each has exactly N1 upstream edges and K = N1 N2 . Part (iii): each side-A server contributes P (Qn ̸= 0) = 1 − p. For a side-B server, we have (d↓n = 0, Un = N1 ). Substituting all these into (18): N1 (2p − 1) pN1 N1 N2 − (46) P (Qn = 0) = N1 N2 p pN1 −1 1 + p(N2 − 2) = . (47) N2 Summing over all N1 + N2 servers gives (45). Remark 7. The expected download (45) satisfies N1 N2 E DKN1 ,N2 12 = +N2 − N1 , E DKN1 ,N2 (1) = 1, 2 2 (48) giving R(1/2) = (N1 /2 + N2 − N2 /2N1 )−1 and R(1) = 1. At p = 1/2: (2p − 1) = 0, so P (Qn = 0) = (1/2)N1 per side-B server; using 1 + (1/2)(N2 − 2) = N2 /2 gives the first expression. At p = 1, side-A adds nothing to the total download, each side-B server has P (Qn ̸= 0) = 1/N2 , giving E[D] = 1. □ VI. C ONCLUSION In this work, we have initiated the study of rate-privacy tradeoffs for PIR on graph-based storage. Clearly, multiple directions of further work exist, including obtaining informationtheoretic converses for WPIR on graphs, improved schemes, and schemes for special graphs. Further, PIR for collusion of servers in graph-based storage and other generalizations remains largely open. R EFERENCES [1] H. Sun and S. A. Jafar, “The capacity of private information retrieval,” IEEE Transactions on Information Theory, vol. 63, no. 7, pp. 4075– 4088, 2017. [2] ——, “The capacity of robust private information retrieval with colluding databases,” IEEE Transactions on Information Theory, vol. 64, no. 4, pp. 2361–2370, 2017. [3] K. Banawan and S. Ulukus, “The capacity of private information retrieval from coded databases,” IEEE Transactions on Information Theory, vol. 64, no. 3, pp. 1945–1956, 2018. [4] C. Tian, H. Sun, and J. Chen, “Capacity-achieving private information retrieval codes with optimal message size and upload cost,” IEEE Transactions on Information Theory, vol. 65, no. 11, pp. 7613–7627, 2019.
[5] R. Zhou, C. Tian, H. Sun, and T. Liu, “Capacity-achieving private information retrieval codes from mds-coded databases with minimum message size,” IEEE Transactions on Information Theory, vol. 66, no. 8, pp. 4904–4916, 2020. [6] N. Raviv, I. Tamo, and E. Yaakobi, “Private information retrieval in graph-based replication systems,” IEEE Transactions on Information Theory, vol. 66, no. 6, pp. 3590–3602, 2020. [7] B. Sadeh, Y. Gu, and I. Tamo, “Bounds on the capacity of private information retrieval over graphs,” IEEE Transactions on Information Forensics and Security, vol. 18, pp. 261–273, 2023. [8] G. Ge, H. Wang, Z. Xu, and Y. Zhang, “Private information retrieval over graphs,” 2025. [Online]. Available: https://arxiv.org/abs/2509.26512 [9] X. Kong, S. Meel, T. J. Maranzatto, I. Tamo, and S. Ulukus, “New capacity bounds for pir on graph and multigraph-based replicated storage,” IEEE Transactions on Information Theory, vol. 72, no. 1, pp. 691–709, 2026. [10] Y. Yao and S. A. Jafar, “The capacity of 4-star-graph pir,” in 2023 IEEE International Symposium on Information Theory (ISIT), 2023, pp. 1603–1608. [11] S. Meel, X. Kong, T. J. Maranzatto, I. Tamo, and S. Ulukus, “Private information retrieval on multigraph-based replicated storage,” in 2025 IEEE International Symposium on Information Theory (ISIT). IEEE, 2025, pp. 1–6. [12] S. Meel and S. Ulukus, “Effect of full common randomness replication in symmetric pir on graph-based replicated systems,” 2025. [Online]. Available: https://arxiv.org/abs/2510.25736 [13] V. Shanbhag and P. Krishnan, “Private information retrieval for graph-based replication with minimal subpacketization,” arXiv preprint arXiv:2601.09957, 2026. [14] H.-Y. Lin, S. Kumar, E. Rosnes, A. Graell i Amat, and E. Yaakobi, “Multi-server weakly-private information retrieval,” IEEE Transactions on Information Theory, vol. 68, no. 2, pp. 1197–1219, 2022. [15] Z. Jia, “On the capacity of weakly-private information retrieval,” Master’s thesis, UC Irvine, 2019. [16] I. Samy, M. Attia, R. Tandon, and L. Lazos, “Asymmetric leaky private information retrieval,” IEEE Transactions on Information Theory, vol. 67, no. 8, pp. 5352–5369, 2021. [17] I. Issa, A. B. Wagner, and S. Kamath, “An operational approach to information leakage,” IEEE Transactions on Information Theory, vol. 66, no. 3, pp. 1625–1657, 2020. [18] B. Köpf and D. Basin, “An information-theoretic model for adaptive side-channel attacks,” in Proceedings of the 14th ACM conference on Computer and communications security, 2007, pp. 286–296. [19] S. Chen, H. Jia, and Z. Jia, “A capacity result on weakly-private information retrieval,” in 2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 2868–2873. [20] C. Anand, J. Seshadri, P. Krishnan, and G. R. Kurri, “Sun-jafartype schemes for weak private information retrieval,” in 2025 IEEE International Symposium on Information Theory (ISIT). IEEE, 2025, pp. 1–6. [21] ——, “Converse bounds for sun-jafar-type weak private information retrieval,” 2026. [Online]. Available: https://arxiv.org/abs/2601.10643 [22] A. O. Orvedal, H.-Y. Lin, and E. Rosnes, “Weakly-private information retrieval from mds-coded distributed storage,” in International Zurich Seminar on Information and Communication (IZS 2024), 2024, p. 40. [23] R. Zhou, T. Guo, and C. Tian, “Weakly private information retrieval under the maximal leakage metric,” in 2020 IEEE International Symposium on Information Theory (ISIT), 2020, pp. 1089–1094. [24] Y.-S. Huang, W. Zhao, R. Zhou, and C. Tian, “Weakly private information retrieval from heterogeneously trusted servers,” in 2024 IEEE International Symposium on Information Theory (ISIT), 2024, pp. 2862– 2867. [25] W. Zhao, Y.-S. Huang, C. Tian, and A. Sprintson, “Optimizing leaky private information retrieval codes to achieve o(log k) leakage ratio exponent,” in 2025 IEEE International Symposium on Information Theory (ISIT), 2025, pp. 1–6.