Local Private Information Retrieval: A New Privacy Perspective for Graph-Based Replicated Systems Shreya Meel
Mohamed Nomeir
Sennur Ulukus
arXiv:2605.10872v1 [cs.IT] 11 May 2026
Department of Electrical and Computer Engineering University of Maryland, College Park, MD 20742 [email protected] [email protected] [email protected]
Abstract—We rethink the definition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems, and introduce a novel setting where the user’s privacy is governed by the servers’ storage structure. In particular, while retrieving a message from a server, the user is concerned with hiding their desired message index from the server, only if the server stores the corresponding message. We coin this privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph. Our goal is to measure the gain in communication efficiency of local PIR, compared to that of canonical PIR, by establishing its capacity, i.e., the maximum number of message symbols retrieved, per downloaded symbol. To this end, we observe a remarkable gain in the local PIR capacity of graphs, that are disjoint union of distinct graphs, which is multiplicative, compared to the PIR capacity, when the individual graphs are identical. For connected graphs, we propose schemes to establish capacity lower bounds for edge-transitive and bipartite graphs, which are greater than the best-known PIR capacity bounds. Finally, we derive the exact local PIR capacity for the cyclic graph, and the path graph with an odd number of vertices.
I. I NTRODUCTION Private information retrieval (PIR) [1] is the framework where a user downloads their desired message from an indexed database, while hiding its index from the database. This problem is motivated by crucial applications where knowing the user’s request reveals the user’s interest, which is detrimental to the user’s privacy. The PIR system model consists of N servers storing K messages, where the user communicates with the servers to retrieve one of these messages privately. PIR has garnered renewed interest among the informationtheoretic community, with the goal of studying its capacity, under various settings. The capacity of PIR, defined as the maximum ratio between the message size, and the amount of downloaded information, was derived in [2] for the fullyreplicated database setting, where the N servers store all K messages. This was extended to address other security concerns, like, database security [3]–[5], server collusion [6]– [12], eavesdroppers [13]–[15], malicious servers [16], [17]. However, as the amount of data keeps growing at a rapid pace, the assumption that all messages are stored at all servers is becoming expensive and unrealistic. Moreover, geographical and access constraints may restrict the storage of some data at certain servers. To address this, PIR with non-fully-replicated databases was introduced in [18], [19], where the storage of messages at the servers is modeled by a hypergraph. Specifically, the servers are represented by vertices, and each
message is represented by a hyper-edge connecting to vertices, corresponding to the servers where the message is replicated. This model was specialized to simple graphs, where each edge consists of exactly two vertices, i.e., each message is stored in two servers [20]–[24], and to r-multigraphs [24], [25] (where each edge is replaced by r parallel edges), and capacity bounds were established for well-known graphs and multigraphs. Although hypergraph-replicated PIR accommodates partial replication of messages, the privacy requirement has been kept the same as the one in the full-replication formulation in [2]. Consequently, it mandates the retrieval of all messages to be uniformly private at all servers, against all message indices, irrespective of whether the given message is stored at the server or not. However, this may be too restrictive towards the goal of preventing user-profiling. From a practical standpoint, if a server does not store a message and is oblivious to its contents, knowing that the user has requested that message is unlikely to breach the user’s privacy. From this viewpoint, we introduce a new perspective to graph-replicated PIR, by studying local PIR, wherein the only message indices that are kept private from a given server are those of the messages that are stored in it. This relaxes the privacy constraint, and increases the capacity for a given graph. Note that, our formulation extends seamlessly to the fully-replicated setting, where local PIR is equivalent to the original PIR formulation. In this work, we focus on simple graphs, and derive local PIR capacity bounds for well-known graph families. First, if a graph is a disjoint union of multiple graphs, we establish a direct connection between the capacity of the overall graph, and that of each individual graph. For connected graphs, i.e., graphs in which there is a path between every pair of vertices, we propose achievable local PIR schemes for edge-transitive and bipartite graphs. These two graph families subsume the graphs whose PIR capacity is known exactly, or up to a constant factor, enabling us to show that local PIR capacity is greater. Moreover, we derive the local PIR capacity for the cyclic graph with N vertices to be 21 , i.e., independent of the number of servers, while its PIR capacity is N2+1 [19]. For the path graph, we establish the local PIR capacity exactly as N −1 2 2N −4 for odd N , compared to N as its PIR capacity [22]. II. P ROBLEM F ORMULATION In graph-replicated PIR systems, each server stores only a subset of the message set W = {W1 , . . . , WK }. Each message
Wk ∈ W is replicated exactly twice and stored on two distinct servers in [N ] = {1, 2, . . . , N }. We represent the database system by a simple, undirected graph G = (V, E), where V = [N ], and |E| = K. Hence, each vertex represents a server and each edge {i, j} ∈ E incident with servers i and j, is assigned the index of the message replicated at those servers. Each message Wk is an independent vector of L independent, and uniformly random symbols from a finite field Fq , with H(W1 , . . . , WK ) =
K X
H(Wk ) = KL
(1)
k=1
in q-ary units. We denote the subset of messages at server n as Wn . Similarly, we denote the message indices in Wn as In = {ℓ : Wℓ ∈ Wn } ⊆ [K].
(2)
Let θ ∈ [K] be the message index required by the user, where θ is uniformly random over [K]. In PIR, to retrieve the [θ] message Wθ , the user sends the query Qn to server n ∈ [N ]. The set of queries for all servers across all θ, denoted by [θ] Q = {Qn , n ∈ [N ], θ ∈ [K]} is independent of the stored messages at the servers, i.e., I(Q; W1 , . . . , WK ) = 0.
(3)
Recall that, in the canonical formulation of graph-replicated PIR, the query sent to server n must satisfy I(θ; Q[θ] n , W1 , . . . , WK ) = 0,
n ∈ [N ].
(4)
In contrast, we introduce the local user privacy requirement where the user’s privacy against server n concerns only with the messages stored in Wn . That is, when the user requests for one of the messages in Wn , server n learns nothing beyond [θ] knowing that θ ∈ In . For local user privacy, Qn must satisfy I(θ; Q[θ] n , Wn | θ ∈ In ) = 0,
n ∈ [N ].
(5)
It is important to note that, in the canonical graph-replicated [θ] / In ) = 0, in PIR system also requires I(θ; Qn , Wn | θ ∈ addition to (5), which is the key difference from our local privacy definition. Upon receiving the query, server n responds with the answer [θ] [θ] An , which is a deterministic function of Qn and Wn , i.e., [θ] H(A[θ] n |Qn , Wn ) = 0.
(6)
As in the usual PIR, from all the received answers, i.e., [θ] [θ] [θ] A[N ] = {A1 , . . . , AN }, and for any realization of θ ∈ [K], the message Wθ should be exactly recovered by the user, i.e., [θ] H(Wθ |A[N ] , Q) = 0.
(7)
A local PIR scheme Π on a graph G is identified by the set of queries Q, and the corresponding set of answers A = [θ] {An , n ∈ [N ], θ ∈ [K]} which satisfy (3), and (5)-(7). For θ = k, let the total number of q-ary symbols downloaded be PN [k] Dk = n=1 H(An ). Further, let D represent the download cost random variable, associated with the random index θ. Then, given the graph G, the rate of a local PIR scheme Π is
defined as, RΠ (G) =
KL L . = PK E[D] k=1 Dk
(8)
The capacity of local PIR for G is the supremum over all achievable rates, i.e., C(G) = supΠ RΠ (G). Remark 1 Due to the relaxed privacy constraint in (5), we have C(G) ≥ CP IR (G), where CP IR is the PIR capacity with the standard (non-local) privacy constraint. III. M OTIVATING E XAMPLES In this section, we demonstrate the main idea of our formulation through local PIR schemes on well-known graphs. Example 1 (Cyclic graph) Consider the cyclic graph CN for N = 4 with the storage W1 = {W1 , W4 }, W2 = {W1 , W2 }, W3 = {W2 , W3 } and W4 = {W3 , W4 }. Assume L = 2 and let W1 = (a1 , a2 ), W2 = (b1 , b2 ), W3 = (c1 , c2 ) and W4 = (d1 , d2 ) be the messages, after the user independently permutes the message symbols, uniformly at random. Table I illustrates the local PIR answers. Note that, privacy against server n is maintained for indices in In . The rate of the scheme is 21 , which is actually the capacity of this setting, while CP IR (C4 ) = 52 < 12 = C(C4 ). θ=1 θ=2 θ=3 θ=4
server 1 a1 + d1 a1 d1 a1 + d1
server 2 a2 + b1 a1 + b1 b1 a1
server 3 b1 b2 + c 1 b1 + c 1 c1
server 4 d1 c1 c2 + d 1 c1 + d 2
TABLE I: Retrieval scheme for C4 .
Example 2 (Complete graph) In a complete graph KN , an edge exists between each vertex pair, thus the total number of edges is N2 . Equivalently, a message is stored at every pair of servers. Consider the case of N = 4, i.e., K4 , where the storage is W1 = {W1 , W2 , W3 }, W2 = {W1 , W4 , W5 }, W3 = {W2 , W4 , W6 } and W4 = {W3 , W5 , W6 }. Assume L = 4, and let the permuted message symbols be W1 = (a1 , . . . , a4 ), W2 = (b1 , . . . , b4 ), W3 = (c1 , . . . , c4 ), W4 = (d1 , . . . , d4 ), W5 = (e1 , . . . , e4 ) and W6 = (f1 , . . . , f4 ). The answers of a local PIR scheme are shown in Table II. The rate of the scheme is 52 , which is greater than the upper bound on the PIR capacity, which is 0.35 ≤ CP IR (K4 ) ≤ 0.3529 by [24]. Example 3 (Star graph) A star graph SN consists of a central server (say server N ) storing all the messages, i.e., WN = {W1 , . . . , WN −1 }, and N − 1 dedicated servers, each storing a single message, i.e., Wn = {Wn } for n ∈ [N − 1]. Then, we have the following local PIR scheme. For θ ∈ [N −1], we query only server θ for Wθ , and do not download anything from server N . For each θ = k, Dk = L, which yields√ the local PIR rate 1. In contrast, the PIR capacity is Θ(1/ N ) [20]. Intuitively, this is because, each server that the user interacts with has only one message, i.e., |In | = 1, n ∈ [N − 1].
θ=4
server 1 a1 + b1 a2 + c1 b2 + c 2 a1 + b1 a2 + c1 b2 + c 2 a1 + b1 a2 + c1 b2 + c 2 a1 b1
θ=5
a2 c1
θ=6
b2 c2
θ=1
θ=2
θ=3
server 2 a3 + d1 a4 + e1 d2 + e2 a1 d1 a2 e1 a1 + d1 a2 + e1 d2 + e2 a1 + d1 a2 + e1 d2 + e2 d2 e2
server 3 b1 d1
server 4 c1 e1
b3 + d1 b4 + f1 d2 + f2 b2 f1
c1 f1
b1 + d3 b2 + f1 d4 + f2 d2 f2 b1 + d1 b2 + f1 d2 + f2
respective |Ei | messages. Then, the local PIR capacity of G is given by, Pm |Ei | · Li . (11) C(G) = Pmi=1 |E i | · E[Di ] i=1 Proof: We present the proof for m = 2, and the case of m > 2 follows by induction. Let E1 = [K1 ] and E2 = [K1 + 1 : K1 + K2 ]. Then, the scheme Π can be described as follows. Given k ∈ E1 ∪ E2 , the user follows the optimal local PIR scheme on G1 if k ∈ E1 and the optimal local PIR scheme on G2 if k ∈ E2 , which yields the rate in (11). Suppose, for the sake of contradiction, that there exists a scheme Π′ that ′ 1 |L1 +|E2 |L2 achieves RΠ (G) > |E1|E |E[D1 ]+|E2 |E[D2 ] . Then, if V2 = ∅, we ′ L1 have G = G1 , and that C(G) ≥ RΠ (G) > E[D . This leads 1] L1 to a contradiction, since C(G) = C(G1 ) is at most E[D , 1] ′ hence, no such Π exists. ■
c3 + e1 c4 + f1 e2 + f 2 e2 f2 c1 + e3 c2 + f1 e4 + f 2 c1 + e1 c2 + f3 e2 + f 4
Corollary 1 If the m graphs G1 , . . . , Gm are identical, then C(G) = C(G1 ), i.e., there is no reduction in capacity. This gives multiplicative gain compared to the PIR capacity in the 1 same setting, since C(G) ≥ CP IR (G) = m CP IR (G1 ) [22].
TABLE II: Retrieval scheme for K4 .
IV. M AIN R ESULTS We start with some useful definitions. Then, we provide the capacity result on disjoint union of graphs, followed by results on important families of connected graphs. Definition 1 (Disjoint union of graphs) Graph G = (V, E) is a disjoint union of m graphs Gi = (Vi , Ei ), i ∈ [m], if Vi ∩ Vj = ∅, i, j ∈ [m], i ̸= j, m m [ [ V = Vi , E = Ei . i=1
(9) (10)
In an edge-transitive graph G, for each k ∈ [K], let i and j be the two servers where Wk is replicated, i.e., {k} = Ii ∩ Ij . Consider the subgraph Gk = G(Vk , Ek ) ⊆ G(V, E) with Vk = {m ∈ [N ] : Im ∩ (Ii ∪ Ij ) ̸= ∅},
(12)
Ek = {ℓ ∈ [K] : ℓ ∈ Ii ∪ Ij },
(13)
i.e., Vk is the set of servers sharing at least one message with server i or server j, including servers i and j, and Ek is the set of messages stored at server i or server j. If G is edgetransitive, Gk is identical for all k ∈ [K].
i=1
Definition 2 (Bipartite graphs) Graph G = (V, E) is bipartite, if the vertex set V is a disjoint union of two sets V1 and V2 , and every edge {i, j} ∈ E, has i ∈ V1 and j ∈ V2 . Examples of bipartite graphs are cyclic graphs with even N , path graphs, star graphs and complete bipartite graphs. Given a graph G = (V, E), its vertex cover is a subset of vertices V ′ ⊆ V such that every edge in E has at least one end point in V ′ . Note that, V1 and V2 are vertex covers of G, which are also independent sets of G, i.e., they share no common edge.
Theorem 2 For edge-transitive graph G, and a fixed edge k ∈ E, where Wk is replicated at servers i and j, the local PIR capacity is lower bounded as deg(i) C(G) ≥ max λ(ti , tj ) + ti − 1 ti ti ∈[deg(i)],tj ∈[deg(j)] deg(j) −1 + (1 − λ(ti , tj )) + tj − 1 , (14) tj where
λ(ti , tj ) = Definition 3 (Edge-transitive graphs) Graph G = (V, E) is edge-transitive, if for every pair of edges e1 , e2 ∈ E there exists an automorphism that maps e1 to e2 . Examples of edge-transitive graphs are cyclic graphs, star graphs, complete graphs and complete bipartite graphs. Sm Theorem 1 Let G = i=1 Gi , where Gi = (Vi , Ei ). Let the capacity-achieving local PIR scheme on Gi entail the message length Li , and the expected download cost E[Di ] for the
deg(i)−1 t −1 i deg(j)−1 . deg(i)−1 + tj −1 ti −1
(15)
The proof of Theorem 2 follows from the achievable scheme given in Section V-A. Remark 2 If deg(i) = deg(j) = d for all Gk , by setting ti = tj = t, (14) can be simplified to 1 1 . (16) √ √ C(G) ≥ max d , d √ √ + ⌊ d⌋ − 1 + ⌈ d⌉ − 1 ⌊ d⌋ ⌈ d⌉
Theorem 5 For the path graph PN , we have
The proof of Remark 2 is presented in Appendix A. Corollary 2 From Theorem 2, we obtain the following rates: 1) For the cyclic graph G = CN , the subgraph Gk = P4 , i.e., the path graph with 4 vertices, where deg(i) = deg(j) = 2, which yields C(CN ) ≥
1 , 2
(17)
which is equal to CP IR (CN ) = N2+1 if N = 3, and strictly greater for all N ≥ 4. 2) For the complete graph G = KN , deg(i) = deg(j) = N − 1, which yields 1 , (18) C(KN ) ≥ √ 2 N −1 1 while 43 − o(1) N1 ≤ CP IR (KN ) ≤ N (e−2) , as recently established in [24]. 3) For the complete, balanced bipartite graph G = K N , N 2 2 for even N , deg(i) = deg(j) = N2 , which yields 2 C(K N , N ) ≥ √ , 2 2 N
(19)
4 1 while 3N ≤ CP IR (K N , N ) ≤ N (e0.5 −1) , by the tightest 2 2 lower and upper bounds, established in [23] and [24], respectively.
Theorem 3 For the cyclic graph CN , we have C(CN ) =
1 . 2
(20)
The achievability of Theorem 3 follows from Theorem 2 and the converse is derived in Section VI. The next result focuses on bipartite graphs. The proof of Theorem 4 is presented in Section V-B. Theorem 4 If G = (V, E) is bipartite, with sets V1 , V2 , the local PIR capacity is lower bounded as !−1 X 2 C(G) ≥ K · min deg(n) . (21) m∈{1,2}
n∈Vm
Corollary 3 From Theorem 4, we have the following rates: 1) For the star graph SN , the scheme achieves C(SN ) = 1,
(22)
by choosing V1 = {1, . . . , N − 1} and V2 = {N }, since deg(n) = 1 for each n ∈ V1 , and K = N − 1. This is the capacity since trivially, C(G) ≤ 1 for any G. 2) For the path graph PN , the scheme yields ( N −1 −3 , N even, C(PN ) ≥ 2N (23) N −1 2N −4 , N odd, which is greater than CP IR (PN ) = N2 , by choosing V1 as the odd, and V2 as the even vertex indices in [N ].
N −1 , 2N − 4 which is tight for odd N settling the capacity. C(PN ) ≤
(24)
The proof of Theorem 5 relies on similar ideas as the converse proof of Theorem 3, and is provided in Appendix D. For odd N , Theorem 5 gives the capacity as the upper bound in (24) matches the rate in (23) for odd N . V. ACHIEVABILITY P ROOFS A. Proof of Theorem 2 We present the scheme for a fixed Gk where {k} = Ii ∩ Ij when θ = k. By edge-transitivity of G, the same scheme applies to all Gk . The user communicates only with the servers in Vk and downloads only the messages corresponding to Ek , i.e., Wi ∪ Wj . We fix ti , tj ∈ N, with ti ∈ [deg(i)] and tj ∈ [deg(j)]. Let each message consist of deg(i) − 1 deg(j) − 1 L= + (25) ti − 1 tj − 1 symbols. The user applies a private, uniformly random, independent permutation to the message symbols of each message in Wi ∪ Wj , with Wℓ (m) denoting the mth permuted symbol of Wℓ . To servers i and j, the user sends queries for all possible ti -sums of the messages in Wi , and all possible tj sums of the messages in Wj , respectively. In particular, let Ai denote the ordered set of all ti -subsets of Ii , and Aj denote the ordered set of all tj -subsets of Ij , arranged in a fixed lexicographic order. Let Ai = Ai1 , . . . , Ai deg(i) and ( ti ) Aj = Aj1 , . . . , Aj deg(j) . Then, for each ℓ ∈ Ii and each ( tj ) i Ap ∈ Ai , such that ℓ ∈ Aip , we define γℓ (Aip ) as γℓ (Aip ) =
p X
1{ℓ ∈ Aix },
(26)
x=1
i.e., the number of times that ℓ is contained in a subset, up to and including Aip . The same definition extends to Aj . Then, for each A ∈ Ai , the user downloads from server i, X Wℓ (γℓ (A)). (27) ℓ∈A
From server j, for each A ∈ Aj , the user downloads P ( Wk deg(i)−1 + γ (A) + ℓ∈A\{k} Wℓ (γℓ (A)), k ∈ A, k ti −1 P k∈ / A. ℓ∈A Wℓ (γℓ (A)), (28) For each ℓ ∈ Ii , and each ℓ ∈ Ij , γℓ (A) varies from 1 to deg(i)−1 , and from 1 to deg(j)−1 , respectively. From ti −1 tj −1 the servers, Vk \ {i, j}, the user downloads the interference message symbols, that appear in the summations (27) and (28). Specifically, for ℓ ∈ Ii \{k}, define Bℓ,i = {B ∈ Ai : {ℓ, k} ⊆ B}, with Bℓ,j defined similarly with Ij . Then, corresponding to ℓ ∈ Ii \ {k} (or Ij \ {k}), the user downloads the symbols,
{Wℓ (γℓ (B)) : B ∈ Bℓ,i (or Bℓ,j )} from the server storing Wℓ . The total download is X X |Ai | + |Aj | + |Bℓ,i | + |Bℓ,j | ℓ∈Ii \{k}
performed modulo-N , i.e., W0 = WN . Then, for θ = k, the download cost Dk can be bounded as Dk ≥
ℓ∈Ij \{k}
deg(i) deg(j) deg(i) − 2 = + + (deg(i) − 1) ti t ti − 2 j deg(j) − 2 + (deg(j) − 1) (29) tj − 2 deg(i) − 1 deg(i) = + ti − 1 ti − 1 t i deg(j) − 1 deg(j) + + tj − 1 . (30) tj − 1 tj
[k]
H(A[k] n |Q) ≥ H(A[N ] |Q) [k]
= H(Wk , A[N ] |Q)
(38) [k]
= H(Wk |Q) + H(A[N ] |Wk , Q)
(39)
[k] = L + I(W \ {Wk }; A[N ] |Wk , Q),
(40)
[k]
where (38) follows since H(Wk |A[N ] , Q) = 0, and (40) holds [k]
since H(A[N ] |W, Q) = 0. Next, we lower bound the second term in (40), which is the interference in the answers, [k]
I(W \ {Wk }; A[N ] |Wk , Q) [k]
≥ I(Wk−1 , Wk+1 ; A[N ] |Wk , Q)
(41)
[k] [k] = I(Wk−1 ; A[N ] |Wk , Q)d + I(Wk+1 ; A[N ] |Wk , Wk−1 , Q)
(42)
B. Proof of Theorem 4 Given G bipartite, with sets V1 and V2 let X deg(n)2 . m∗ = arg min m∈{1,2}
[k] [k] ≥ I(Wk−1 ; Ak |Wk , Q) + I(Wk+1 ; Ak+1 |Wk , Wk−1 , Q)
(31)
n∈Vm
For θ = k, suppose Wk is stored on servers i and j. Assume without loss of generality that i ∈ Vm∗ and j ∈ / Vm∗ . Then, the user queries for all messages from server i, downloading deg(i) messages and nothing at all from server j. The resulting total download is ! K K X X X Dk = deg(n)L 1{k ∈ In } (32) n∈Vm∗
k=1
=
(37)
n=1
The ratio between (25) and (30) gives the desired rate. The rate is maximized over ti and tj to obtain the largest lower bound. Privacy holds at servers i and j since the same scheme is followed for all θ in Ii and Ij , respectively.
N X
X
(43) [k−1] [k+1] = I(Wk−1 ; Ak |Wk , Q) + I(Wk+1 ; Ak+1 |Wk , Wk−1 , Q)
(44) [k−1] [k+1] = H(Ak |Wk , Q) + H(Ak+1 |Wk , Wk−1 , Q),
where (44) follows from Lemma 1 and Lemma 2, and (45) [k] follows since H(An |Wn , Wn−1 , Q) = 0 for all n, k ∈ [N ]. Summing Dk − L over all k ∈ [N ], we have, N X
k=1
deg(n)2 L.
(33)
The ratio between KL and (33) gives the desired rate. VI. C ONVERSE P ROOF FOR C YCLIC G RAPHS
=
We start with the following lemmas, which any feasible local PIR scheme should satisfy. The first lemma is a consequence of local user privacy, while the second lemma follows [k] [k] from the fact that An is independent of Q given Qn . The proofs are given in Appendices B and C, respectively. Lemma 1 For any J ⊆ [K], define the message set WJ = {Wℓ : ℓ ∈ J }. Then, we have [θ] I(θ; A[θ] n |Qn , WJ ) = 0,
θ ∈ In , n ∈ [N ].
[k] [k] [k] H(A[k] n |WJ , Qn ) = H(An |WJ , Qn , Q) = H(A[k] n |WJ , Q).
≥ ≥
=
(34)
Lemma 2 For any subset J ⊆ [K], any k ∈ [K], n ∈ [N ] (35) (36)
We now prove Theorem 3. Let Wn = {Wn , Wn−1 }, where the subtraction is taken modulo-N . Moreover, throughout the proof, we assume that the additions and subtractions are
Dk − N L
k=1
≥
n∈Vm∗
(45)
=
N X k=1 N X k=1 N X k=1 N X k=1 N X k=1 N X
[k−1]
H(Ak
[k+1]
|Wk , Q) + H(Ak+1 |Wk , Wk−1 , Q) (46)
[k]
[k]
H(Ak |Wk−1 , Wk−2 , Q) + H(Ak+1 |Wk+1 , Q) (47) [k]
[k]
(48)
[k]
[k]
(49)
H(Ak , Ak+1 |Wk−2 , Wk−1 , Wk+1 , Q) H(Ak , Ak+1 |W \ {Wk }, Q) [k]
[k]
H(Wk , Ak , Ak+1 |W \ {Wk }, Q) [k]
(50) [k]
H(Wk |W \ {Wk }, Q) + H(Ak , Ak+1 |W, Q) (51)
k=1
= N L,
(52)
where (47) follows by collecting the answers with the same index k, (50) holds from decodability of Wk since the answers [k] A[N ]\{k,k+1} are deterministic functions of W \ {Wk } and Q. Finally, the second term of (51) is zero, completing the proof.
R EFERENCES [1] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval. Journal of the ACM, 45(6):965–981, November 1998. [2] H. Sun and S. A. Jafar. The capacity of private information retrieval. IEEE Trans. Inf. Theory, 63(7):4075–4088, March 2017. [3] H. Sun and S. A. Jafar. The capacity of symmetric private information retrieval. IEEE Trans. Inf. Theory, 65(1):322–329, June 2018. [4] Q. Wang and M. Skoglund. Symmetric private information retrieval from MDS coded distributed storage with non-colluding and colluding servers. IEEE Trans. Inf. Theory, 65(8):5160–5175, March 2019. [5] Z. Wang and S. Ulukus. Symmetric private information retrieval at the private information retrieval rate. IEEE J. Sel. Areas Inf. Theory, 3(2):350–361, October 2022. [6] H. Sun and S. A. Jafar. The capacity of robust private information retrieval with colluding databases. IEEE Trans. Inf. Theory, 64(4):2361– 2370, April 2018. [7] Q. Wang and M. Skoglund. On PIR and symmetric PIR from colluding databases with adversaries and eavesdroppers. IEEE Trans. Inf. Theory, 65(5):3183–3197, October 2019. [8] R. Freij-Hollanti, O. W. Gnilke, C. Hollanti, and D. A. Karpuk. Private information retrieval from coded databases with colluding servers. SIAM J. Appl. Algebra and Geometry, 1(1):647–664, 2017. [9] X. Yao, N. Liu, and W. Kang. The capacity of private information retrieval under arbitrary collusion patterns for replicated databases. IEEE Trans. Inf. Theory, 67(10):6841–6855, July 2021. [10] Z. Jia, H. Sun, and S. A. Jafar. Cross subspace alignment and the asymptotic capacity of X-secure T -private information retrieval. IEEE Trans. Inf. Theory, 65(9):5783–5798, May 2019. [11] M. Nomeir, S. Vithana, and S. Ulukus. Asymmetric X-secure T -private information retrieval: More databases is not always better. In CISS, March 2024. [12] M. Nomeir, A. Aytekin, and S. Ulukus. The capacity of semantic private information retrieval with colluding servers. In IEEE GLOBECOM, December 2025. [13] Q. Wang, H. Sun, and M. Skoglund. The capacity of private information retrieval with eavesdroppers. IEEE Trans. Inf. Theory, 65(5):3198–3214, December 2018. [14] J. Cheng, N. Liu, W. Kang, and Y. Li. The capacity of symmetric private information retrieval under arbitrary collusion and eavesdropping patterns. IEEE Trans. Inf. Forensics Security, 17:3037–3050, August 2022. [15] Q. Wang, H. Sun, and M. Skoglund. The capacity of private information retrieval with eavesdroppers. IEEE Trans. Inf. Theory, 65(5):3198–3214, December 2018. [16] K. Banawan and S. Ulukus. The capacity of private information retrieval from Byzantine and colluding databases. IEEE Trans. Inf. Theory, 65(2):1206–1219, September 2018. [17] M. Nomeir, A. Aytekin, and S. Ulukus. The asymptotic capacity of Byzantine symmetric private information retrieval and its consequences. In IEEE ISIT, June 2025. [18] N. Raviv, I. Tamo, and E. Yaakobi. Private information retrieval in graphbased replication systems. IEEE Trans. Inf. Theory, 66(6):3590–3602, November 2019. [19] K. Banawan and S. Ulukus. Private information retrieval from nonreplicated databases. In IEEE ISIT, July 2019. [20] B. Sadeh, Y. Gu, and I. Tamo. Bounds on the capacity of private information retrieval over graphs. IEEE Trans. Inf. Forensics Security, 18:261–273, November 2023. [21] Y. Yao and S. A. Jafar. The capacity of 4-star-graph PIR. In IEEE ISIT, June 2023. [22] 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 Trans. Inf. Theory, 72(1):691–709, January 2026. [23] V. Shanbhag and P. Krishnan. Private information retrieval for graphbased replication with minimal subpacketization, 2026. Available online at arXiv:2601.09957. [24] G. Ge, H. Wang, Z. Xu, and Y. Zhang. Private information retrieval over graphs, 2025. Available online at arXiv:2509.26512. [25] S. Meel, X. Kong, T. J. Maranzatto, I. Tamo, and S. Ulukus. Private information retrieval on multigraph-based replicated storage. In IEEE ISIT, June 2025.
A PPENDIX
C. Proof of Lemma 2 [k]
A. Proof of Remark 2 The expression that we minimize is d d λ(ti , tj ) + ti − 1 + (1 − λ(ti , tj )) + tj − 1 , ti tj (53)
[k]
For (35), we show that I(An ; Q|WJ , Qn ) = 0. Denoting Wn′ as Wn ∩ WJ , we have [k] I(A[k] n ; Q|WJ , Qn ) ′ [k] ≤I(A[k] n , Wn \ Wn ; Q|WJ , Qn )
(66)
[k] ′ [k] =I(Wn \ Wn′ ; Q|WJ , Q[k] n )+I(An ; Q|Wn , WJ \ Wn , Qn )
(67)
where d−1 ti −1
λ(ti , tj ) =
d−1 ti −1
∈ (0, 1). d−1
+ tj −1
(54)
Assume without loss of generality, that tdi +ti −1 ≤ tdj +tj −1. Now, for any λ(ti , tj ) ∈ (0, 1), d d λ(ti , tj ) + ti − 1 + (1 − λ(ti , tj )) + tj − 1 t tj i d d ≥ min + ti − 1, + tj − 1 (55) ti tj d (56) = + ti − 1, ti The minimum value of (56) is achieved by setting ti = tj = t in (53), and solving 1 . + t−1 t
max d t∈[d]
(57)
The solutiono of (57) yields the optimal value of t ∈ n √d , √d , which completes the proof. ⌈ d⌉ ⌊ d⌋
[k] ≤I(Wn \ Wn′ ; Q|WJ , Q[k] n ) + I(WJ ; Q|Qn ) =I(Wn , WJ \ Wn′ ; Q|Q[k] n ) ′ ≤I(Wn , WJ \ Wn ; Q, Q[k] n ) = 0,
(68) (69) (70)
where (68) follows since the second term of (67) is zero [k] [k] because H(An |Wn , WJ \Wn′ , Qn ) = 0, and the last equality [k] follows by (3). The equality (36) holds since H(Qn |Q) = 0.
D. Proof of Theorem 5 Given PN , let the storage of the servers be n = 1, {W1 }, Wn = {Wn , Wn−1 }, n ∈ [2 : N − 1], {WN −1 }, n = N.
(71)
For θ = k, following steps as in (37)–(40), we obtain [k]
Dk ≥ L + I(W \ {Wk }; A[N ] |Wk , Q).
(72)
Next, we lower bound the second term. First, for k = 1,
B. Proof of Lemma 1
[1]
It is equivalent to showing that for any k, k ′ ∈ In , k ̸= k ′ , ′
′
[k] [k ] [k ] H(A[k] n |Qn , WJ ) = H(An |Qn , WJ ).
[1]
I(W \ {W1 }; A[N ] |W1 , Q) ≥ I(W2 ; A[N ] |W1 , Q)
(73)
[1] ≥ I(W2 ; A2 |W1 , Q) [1] = H(A2 |W1 , Q) [2] = H(A2 |W1 , Q).
(74)
(58)
Let Wn′ = Wn ∩ WJ . Note that, [k] H(A[k] n |Qn , WJ ) [k] ′ ′ [k] [k] ′ = H(A[k] n |Qn , Wn ) − I(WJ \ Wn ; An |Qn , Wn )
(59)
[k] ′ = H(A[k] n |Qn , Wn ),
(60)
since
(62) (63)
= 0.
(64)
[N −2]
|WN −1 , Q) ≥ H(AN −1 |WN −1 , Q). (77)
I(W \ {Wk }; A[N ] |Wk , Q) [k]
(78)
[k] [k] = I(Wk−1 ; A[N ] |Wk , Q) + I(Wk+1 ; A[N ] |Wk , Wk−1 , Q)
(79) [k] [k] ≥ I(Wk−1 ; Ak |Wk , Q) + I(Wk+1 ; Ak+1 |Wk , Wk−1 , Q)
(80)
From (5) and (6), for every n and θ ∈ In ,
Finally, combining (60) and (65) proves the lemma.
[N −1]
I(W \ {WN −1 }; A[N ]
≥ I(Wk−1 , Wk+1 ; A[N ] |Wk , Q)
[k] [k] ≤ I(WJ \ Wn′ ; Wn |Q[k] n ) + H(An |Qn , Wn )
[θ] [θ] [θ] ′ 0 = I(θ; Q[θ] n , An , Wn ) ≥ I(θ; Qn , An , Wn ).
Similarly, for k = N − 1, we have
[k]
(61)
′ = I(WJ \ Wn′ ; Wn \ Wn′ |Q[k] n , Wn ) [k] + I(WJ \ Wn′ ; A[k] n |Qn , Wn )
(76)
For k ∈ [2 : N − 2], we have
[k] ′ I(WJ \ Wn′ ; A[k] n |Qn , Wn ) ′ [k] ′ ≤ I(WJ \ Wn′ ; A[k] n , Wn \ Wn |Qn , Wn )
(75)
(65)
[k−1] [k+1] = I(Wk−1 ; Ak |Wk , Q) + I(Wk+1 ; Ak+1 |Wk , Wk−1 , Q)
(81) [k−1] [k+1] = H(Ak |Wk , Q) + H(Ak+1 |Wk , Wk−1 , Q).
(82)
where (81) is due to Lemmas 1 and 2. Now, summing Dk − L over all k ∈ [N − 1], we have N −1 X
Dk − (N − 1)L
k=1 [2]
≥H(A2 |W1 , Q) +
N −2 X
[k−1]
H(Ak
[k+1]
|Wk , Q) + H(Ak+1 |Wk , Wk−1 , Q)
k=2 [N −2]
+ H(AN −1 |WN −1 , Q)
(83)
[2] [2] ≥H(A2 |W1 , Q) + H(A3 |W3 , Q) N −2 X [k] [k] + H(Ak |Wk−1 , Wk−2 , Q) + H(Ak+1 |Wk+1 , Q) k=3
(84) [2] [2] ≥H(A2 , A3 |W1 , W3 , Q) N −2 X [k] [k] + H(Ak , Ak+1 |Wk−2 , Wk−1 , Wk+1 , Q) k=3 [2] [2] ≥H(A2 , A3 |W \ {W2 }, Q)
+
N −2 X
[k]
[k]
H(Ak , Ak+1 |W \ {Wk }, Q)
(85)
(86)
k=3 [2]
[2]
=H(W2 , A2 , A3 |W \ {W2 }, Q) +
N −2 X
[k]
[k]
H(Wk , Ak , Ak+1 |W \ {Wk }, Q)
(87)
k=3 [2]
[2]
=H(W2 |W \ {W2 }, Q) + H(A2 , A3 |W, Q) +
N −2 X
[k]
[k]
H(Wk |W \ {Wk }, Q) + H(Ak , Ak+1 |W, Q)
k=3
(88) =(N − 3)L.
(89) [1]
where (84) follows by dropping the terms H(A2 |W2 , Q) and [N −1] H(AN −1 |WN −3 , WN −2 ), and re-arranging the remaining terms, and (88) holds by decodability, completing the proof.