Private Information Retrieval With Arbitrary Privacy Requirements: Introduction and Capacity Results∗ Mohamed Nomeir
Shreya Meel
Sennur Ulukus
arXiv:2609.15875v1 [cs.IT] 14 Sep 2026
Department of Electrical and Computer Engineering University of Maryland, College Park, MD 20742 [email protected] [email protected] [email protected]
Abstract In this paper, we introduce the problem of private information retrieval (PIR) under arbitrary privacy requirements, in a graph-based storage system. This formulation is motivated by the server storage limitations, abundance of data (messages) and heterogeneous data privacy requirements. Under the arbitrary privacy requirement, each message has to be retrieved privately from a pre-specified subset of servers, where the subset always includes the servers storing it. Thus, each server is associated with a privacy set, which pre-specifies the message indices that should be privately retrieved from it. This setting is a generalization of the classical PIR setting, where the required message index needs to be kept private from all servers, i.e., there, the privacy set of each server comprises all message indices. Our setting is also a bridge between the newly formulated local PIR (LPIR) setting and the classical PIR setting, where in the former, the privacy set is exactly the set of stored message indices. In this paper, we derive general lower and upper bounds on the PIR capacity for general graphs, under certain privacy requirements, that capture the essence of both LPIR and classical PIR. Then, we focus on path and cyclic storage graphs under these and more fine-grained settings, for which we derive capacity results for certain cases, and establish lower and upper bounds for others. Their low degree allows for a more in-depth understanding of the new privacy formulation and admits more privacy requirement settings compared to other simple graphs. Finally, we introduce a new graph structure, the pyramid storage graph, to model server storage. Although this graph has never been investigated in the literature in any PIR context, it enjoys a nice symmetric structure for message storage and replication patterns. In this setting, we provide a capacity lower bound for LPIR. Interestingly, the corresponding scheme is shown to be also valid for two other more stringent privacy settings. ∗
A part of this work was accepted in IEEE ITW 2026.
1
1
Introduction and Motivation
The initial formulation of the private information retrieval (PIR) problem [1] considers N fully-replicated servers, where all K messages are stored at all servers. The goal is to design a scheme to retrieve one out of K messages without letting any individual server know the retrieved message index. The metric is the communication efficiency, i.e., the rate, which is the ratio of the average length of the required message to the average total number of downloaded symbols. The highest achievable rate is called the capacity of PIR. The capacity of the fully-replicated PIR is derived in [2]. Subsequently, several variants of the fullyreplicated PIR under various threat models are analyzed in [3–13], and the corresponding quantum versions are analyzed recently in [14–17]. As a major departure from the fullyreplicated setting, [18] considers the case where the messages are encoded using maximum distance separable (MDS) codes for each message individually and stored in the N servers. For an (M, N ) MDS code, this significantly reduces server storage (by a factor of M ) at the cost of reduced PIR capacity. Even though the server storage is reduced, a portion of every message is still stored in every server; therefore, this may be viewed as a version (coded) of fully-replicated setting. Further, [19] considers the case of jointly encoded storage of messages, where the messages are mixed during encoding. In another line of research, weakly PIR [20, 21] aims to relax the privacy requirement. In weakly PIR, a pre-defined privacy leakage budget is allowed, which provides a higher rate by leveraging the leakage budget. The weakly PIR provides a uniform leakage budget to all messages in the system. As a first real step in moving away from full-replication, [22] introduces the idea of graph PIR (GPIR), where each message is replicated in a subset of servers, i.e., each server holds a subset of messages. This is equivalent to a hyper-graph, where the nodes represent the servers and the hyper-edges represent the messages; each message represented by a hyperedge is stored at the servers that the hyper-edge is incident on. Reference [23] considers a different modeling convention, where the messages are the nodes and the servers are the edges in a graph representation. These works are followed by extended settings for GPIR for simple- and multi-graphs [24–31]. In all the aforementioned formulations, one requirement remained constant: the required message index must be kept private against all servers. This requirement becomes too restrictive when the graph contains a large number of nodes N and when the message replication is limited. This is evident from the available capacity results, where the capacity decays as fast as Θ(1/N ). This motivates the need for a new privacy model to accommodate data abundance, storage limitation, and privacy heterogeneity. Recently, the concept of local privacy and the accompanying local PIR (LPIR) problem have been introduced in [32, 33]. In LPIR, the required message index must be kept private only from the servers that store the required message. For LPIR, [32, 33] show a significant increase in the retrieval rate compared to the conventional GPIR. In the present paper, we define a model that accommodates more general privacy requirements, and encompasses LPIR and GPIR as special cases. The key observation is that, since data is heterogeneous, 2
the privacy budget can also be heterogeneous; for example, retrieving a specific patient’s medical record might require higher privacy than retrieving a movie. Motivated by such real-world settings, we define the problem of PIR with arbitrary privacy requirements, where each message has its own privacy requirement based on its sensitivity. Thus, to fully define a setting in our framework, one needs both the storage pattern and the privacy pattern; that is, even for a fixed storage graph, we may have multiple required privacy patterns. Finally, we note that there are two important differences between our formulation and the weakly PIR formulation: first, in our case, the privacy budget is message-dependent, i.e., each message has its own privacy requirement; second, the requirement is more tangible than assigning an overall privacy-budget value as in the weakly PIR setting, in the sense that, we precisely know which messages must be kept private for each server when being queried. In this paper, we introduce PIR with arbitrary privacy requirements as a generalization of GPIR and LPIR, and establish rate bounds and exact capacity results. First, we provide a general result for any graph, for any privacy requirement, where we optimize over all GPIR schemes, tuned to meet the specific privacy setting. For our subsequent results, we introduce three special settings: extremely private messages, where a subset of messages is kept private from all servers when retrieving, oblivious servers, where a subset of servers have all the messages in their privacy sets, and modified edge-servers privacy, where the privacy sets of the leaves are the same as their parent nodes in graphs that are trees. We present a capacity upper bound for the first setting, and lower bounds for the second and third settings. To derive sharper capacity bounds, we focus on two simple graphs: path and cyclic. Specifically, for the path graph, we identify the exact capacity for the extremely private messages setting with odd N , and the modified edge-servers privacy for all N . For the cyclic graph, we focus on N ≥ 4, since for N = 3, the capacity for any arbitrary privacy setting can be shown to be 12 , due to matching GPIR and LPIR capacities. Furthermore, we derive the exact capacity for the extremely private messages setting, and for certain subsets of oblivious servers. We also define a new privacy setting where the server keeps the ith neighboring server’s storage in its privacy set, and derive the corresponding capacity bounds. For both path and cyclic graphs, we also derive capacity bounds for the one- and two-sided h-neighbor privacy settings, where the privacy set of each server consists of the indices of messages in the storage of up to its hth neighbor. In particular, the two-sided h-neighbor privacy setting renders a transition from LPIR to GPIR setting. Finally, we introduce the pyramid storage graph, which is a non-uniform hypergraph with a symmetrical, pyramid-like storage architecture. This scenario may arise in practical distributed storage systems, where the cost of replicating each message is different. Alternatively, this can reflect a scenario where all messages may be fully-replicated initially, but some of the servers may have outdated or erased versions of some messages, making them unsuitable for retrieval. For this graph, we propose an achievable LPIR scheme, which is also a valid scheme for two other settings of the modified edge-servers privacy.
3
The rest of the paper is organized as follows. Section 2 provides the necessary definitions and the problem formulation. Section 3 provides examples for different privacy settings to motivate and introduce the new framework. Section 4 gives the main results for general graphs. Section 5 presents specific results for path storage graphs and Section 6 presents specific results for cyclic storage graphs. Section 7 introduces and analyzes the pyramid storage graphs. Section 8 concludes the paper and provides directions for future work. Notations: We use calligraphic font to denote sets. [a : b] denotes the set of integers {a, a + 1, a + 2, . . . , b} and [a] denotes the set {1, 2, . . . , a}. In addition, for the family of sets Li , i ∈ I, if Z ⊆ I, then LZ = ∪i∈Z Li . We use CGP IR to denote the usual PIR capacity over a graph; CLP IR to denote the capacity of LPIR; and C without any subscripts to denote the capacity of our formulation. For the specific graph families, we use PN and CN to denote the path graph and the cyclic graph with N nodes, respectively.
2
Problem Formulation
2.1
Preliminaries
Definition 1 (Privacy set) The privacy set Pn of server n is the set of message indices whose privacy should be maintained at server n. Remark 1 Let In denote the set of indices of messages stored in the nth server. Then, In ⊆ Pn ⊆ [K], for all n ∈ [N ]. The case of Pn = In is the setting of local PIR (LPIR), while Pn = [K] is the setting of classical PIR over graphs (GPIR). Definition 2 (Extremely private messages) A message k ∈ [K] is called an extremely private message if it is contained in the privacy sets of all the servers, i.e., k ∈ Pn , for all n ∈ [N ]. The set of all extremely private messages is E, i.e., E = {k ∈ [K] : k ∈ Pn , n ∈ [N ]}. Definition 3 (Oblivious server) A server n ∈ [N ] is called an oblivious server if its privacy set contains all the messages, i.e., Pn = [K]. The set of all oblivious servers is O, i.e., O = {n ∈ [N ] : Pn = [K]}. Definition 4 (Useful side information) Given any GPIR or LPIR scheme Π, the queries sent to any server can be separated into three classes: queries sent to retrieve symbols for the required message index, i.e., the queries containing the required message index θ, the queries sent to be used in decoding the required message symbols (interference alignment), and the queries sent to ensure privacy. Neither the second nor the third kind of queries contain the required message index. The answers received in response to the second kind of queries are called the useful side information. Remark 2 There can be an overlap between the second and third kind of queries in Definition 4, in which case, we consider them as the second kind. 4
2.2
Problem Statement
We consider a system that consists of N non-colluding servers and K independent messages, where the ith message has Li symbols generated uniformly and independently at random, H(W[K] ) =
K X
H(Wi ) =
i=1
K X
Li ,
(1)
i=1
where Wi represents the ith message, and [K] represents the set {1, . . . , K}. As in the case of classical PIR, the user does not have any side information about the message contents, thus, the messages are independent of the queries sent, I(W[K] ; Q) = 0, [k]
(2)
[k]
where Q = {Qn : n ∈ [N ], k ∈ [K]} and Qn is the query sent to the nth server when [k] retrieving the kth message, including the potential null query Qn = ∅. The user transmits [k] the query Qn such that the required message index remains hidden from the intended servers, I(θ; Q[θ] n |θ ∈ Pn ) = 0,
n ∈ [N ],
(3)
where Pn is the privacy set. We note that, if a server is not queried, it does not know that the scheme is initiated. However, since the scheme is globally known, when a query is transmitted to a server, it knows whether a message in its privacy set is being queried or not. The answer generated from server n is a function of its individual storage Wn and the received query, i.e., for all n ∈ [N ], k ∈ [K], [k] H(A[k] n | Wn , Qn ) = 0.
(4)
Once the user receives the answers from all servers, the required message must be decodable, [θ]
H(Wθ |A[N ] , Q) = 0.
(5)
The rate is defined as in the semantic PIR setting since the messages may be of unequal lengths and the downloaded number of symbols for each message may be different, PK E [L] i=1 Li = PK , RΠ = E [D] D i i=1
(6)
where Π is a scheme satisfying (2)-(5) for a given privacy requirement. Since all messages P [i] are equally likely, the rate reduces to the second equality, where Li and Di = N n=1 H(An ) are the ith message length and the number of downloaded symbols when retrieving the ith message, respectively. The capacity C is the supremum of the rate over all such Π.
5
3
Motivating Examples
Example 1 (Cyclic graph with 1st neighbor privacy) Let N = 5, and the storage be given as W1 = {W1 , W5 }, W2 = {W1 , W2 }, W3 = {W2 , W3 }, W4 = {W3 , W4 }, W5 = {W4 , W5 }. The privacy sets are given by P1 = {1, 2, 5}, P2 = {1, 2, 3}, P3 = {2, 3, 4}, P4 = {3, 4, 5}, P5 = {1, 4, 5}.
(7)
The message lengths are chosen as L = 2. Let W1 = (a1 , a2 ), W2 = (b1 , b2 ), W3 = (c1 , c2 ), W4 = (d1 , d2 ) and W5 = (e1 , e2 ) be message symbols after being uniformly and independently permuted by the user. Table 1 shows the retrieval scheme for each message index. The rate is R = 52 , which is greater than the capacity of the cyclic graph CP IR (C5 ) = 31 [23]. The rate is lower than the capacity of local PIR CLP IR (C5 ) = 21 due to the locality property [33]. θ=1 θ=2 θ=3 θ=4 θ=5
server 1 a1 + e 1 a1 + e 1 a1 e1 a1 + e 1
server 2 a2 + b 1 b1 + a 1 b1 + a 1 b1 a1
server 3 b1 b2 + c 1 b1 + c 1 b1 + c 1 c1
server 4 d1 c1 c2 + d 1 c1 + d 1 d1 + c 1
server 5 d1 + e 1 e1 d1 d2 + e 1 d1 + e 2
Table 1: Retrieval scheme for Example 1.
Example 2 (Path graph with modified edge-servers privacy) Let N = 4 servers, then the storage is given as W1 = {W1 }, W2 = {W1 , W2 }, W3 = {W2 , W3 }, W4 = {W3 }. The privacy sets are given by P1 = {1, 2}, P2 = {1, 2}, P3 = {2, 3}, P4 = {2, 3}.
(8)
The message lengths are chosen as L = 2. Table 2 shows the retrieval scheme. The rate is R = 53 , which is greater than the capacity of the path graph CP IR (P4 ) = 12 [27]. We show in Theorem 5 that 53 is indeed the capacity of this setting. θ=1 θ=2 θ=3
server 1 a1 a1
server 2 a2 + b 1 b1 + a 1 b1
server 3 b1 b2 + c 1 b1 + c 1
server 4 c1 c2
Table 2: Retrieval scheme for Example 2.
Example 3 (C5 with two oblivious servers) Given the cyclic storage graph with N = 5 as in Example 1 with storage W1 = {W1 , W5 }, W2 = {W1 , W2 }, W3 = {W2 , W3 }, W4 =
6
{W3 , W4 }, W5 = {W4 , W5 }, and let the first and the third servers be oblivious and the remaining servers follow local privacy, i.e., the privacy sets are given by P1 = {1, 2, 3, 4, 5}, P2 = {1, 2}, P3 = {1, 2, 3, 4, 5}, P4 = {3, 4}, P5 = {4, 5}.
(9)
The message lengths are chosen as L1 = L2 = L3 = L5 = 1 and L4 = 2. For notational consistency, we define W1 = a1 , W2 = b1 , W3 = c1 , W4 = (d1 , d2 ) after permuting, and W5 = e1 . Table 3 shows the optimal retrieval scheme for this setting. The rate is R = 12 , which matches the capacity for this setting. server 1 θ=1 θ=2 θ=3 θ=4 θ=5
server 2 a1 , b1 a1 , b1
server 3
server 4
c1 , d1 c1 , d1
server 5
d2 , e1 d2 , e1
Table 3: Optimal retrieval scheme for Example 3.
Example 4 (C3 with one extremely private message) Consider C3 with W1 as an extremely private message. The storage is W1 = {W1 , W3 }, W2 = {W1 , W2 }, W3 = {W2 , W3 }. Since the first message index is extremely private, the privacy sets are given by P1 = {1, 3}, P2 = {1, 2}, P3 = {1, 2, 3}.
(10)
We choose the message length as L = 12 and the symbols of each message after choosing a permutation uniformly at random are given by W1 = a[12] , W2 = b[12] , and W3 = c[12] . The optimal retrieval scheme is given in Table 4. The rate of the scheme is R = 21 , which is the capacity for this setting.
θ=1
θ=2
θ=3
server 1 a1 , a2 , c1 , c2 , a3 + c3 , a4 + c4 , a5 + c 5 , a 6 + c 6 a3 , a4 , a5 , a6 , c3 , c4 , c5 , c6 a1 , a2 , c7 , c8 , a3 + c9 , a4 + c10 , a5 + c11 , a6 + c12
server 2 a7 , a8 , b1 , b2 , a9 + b3 , a10 + b4 , a11 + b5 , a12 + b6 a1 , a2 , b1 , b2 , a3 + b3 , a4 + b4 , a5 + b 5 , a 6 + b 6 a3 , a4 , a5 , a6 , b3 , b4 , b5 , b6
server 3 b3 , b4 , c3 , c4 , b1 + c5 , b2 + c6 , b5 + c 1 , b 6 + c 2 b7 , b8 , c1 , c2 , b9 + c3 , b10 + c4 , b11 + c5 , b12 + c6 b1 , b2 , c1 , c2 , b3 + c3 , b4 + c4 , b5 + c 5 , b 6 + c 6
Table 4: Optimal retrieval scheme for Example 4.
7
4
Results on General Graphs
We start by the following lemma. Although it is quite intuitive, it shows how the local PIR and GPIR are connected through the setting of arbitrary private sets PIR. Lemma 1 Given a storage hyper-graph G = ([N ], W), where W is the set of messages (hyper-edges) with arbitrary private sets Pn , n ∈ [N ], then the capacity of this setting is upper bounded by the local PIR capacity on G and lower bounded by the GPIR capacity over the graph G, i.e., CGP IR (G) ≤ C ≤ CLP IR (G).
(11)
The proof of Lemma 1 is straightforward as In ⊆ Pn ⊆ [K], i.e., increasing the privacy constraint cannot increase the capacity. Theorem 1 Let ΠP IR be a scheme for GPIR with K messages and Li , i ∈ [K], message ′ lengths and Dn , n ∈ [N ], symbols downloaded from the nth server. In addition, let Dn,k be the amount of useful side information downloaded from the nth server when retrieving the message θ = k. Then, the capacity of PIR with an arbitrary privacy requirement given by Pn , n ∈ [N ], is lower bounded by PK C ≥ max P ΠP IR
k
i=1 Li
P
n 1{k ∈ Pn } · Dn +
′ / Pn } · Dn,k n 1{k ∈
P
(12)
Proof: The proof stems from the fact that any GPIR scheme can be modified to the setting with arbitrary privacy sets Pn , n ∈ [N ], since the privacy requirements are stricter in GPIR. Without loss of generality, let the required index be θ = k, and let Nk be the set of servers that have k in their privacy set, i.e., Nk = {n ∈ [N ] : k ∈ Pn }.
(13)
Since Pn ⊆ [K], we apply the GPIR scheme Π on the servers in Nk , thus downloading Dn for all n ∈ Nk . On the other hand, we download only the clear side information from the servers [N ] \ Nk that can cancel the interference terms from the servers in Nk , to decode Wk . ′ This amounts to Dn,k , for n ∈ [N ] \ Nk . Now, since Π is symmetric for all messages, by virtue of it being a PIR scheme, for any server with any arbitrary message in its privacy set, it will receive the same queries that provide privacy in the GPIR setting. On the other hand, if it does not have the retrieved message index in its privacy set, we download only the specific required side information needed to decode the required message by canceling the interference. ■
8
Theorem 2 Let the privacy sets be defined based on the extremely private messages in E ⊆ [K] and local privacy, i.e., Pn = In ∪ E, for all n ∈ [N ]. In addition, let Dk be the number of downloaded symbols for retrieving k ∈ E using the optimal GPIR scheme Π1 and let Dk′ be the number of downloaded symbols for the optimal local PIR scheme when retrieving k ∈ [K] \ E using the optimal local PIR scheme Π2 , then the capacity for this setting is upper-bounded by P i∈[K] Li P C≤P , (14) ′ k∈E Dk + k∈[K]\E Dk where Li is the length of ith message in the three schemes, i.e, LPIR, GPIR and arbitrary privacy sets PIR. Proof: Consider a feasible scheme for this privacy setting that downloads Dk′′ symbols when retrieving the kth message. Then, the total number of download symbols for all messages can be lower bounded as X
Dk′′ =
X k∈E
k∈[K]
≥
X
X
Dk′′ +
Dk′′
(15)
Dk′ ,
(16)
k∈[K]\E
X
Dk +
k∈E
k∈[K]\E
where (16) is due to the interference upper bounds for each message index and the optimality of the individual schemes. Then, P i∈[K] Li (17) R= P ′′ i∈[K] Di P i∈[K] Li P , (18) ≤P ′ k∈[K]\E Dk k∈E Dk + which completes the proof. ■ Theorem 3 For a simple graph G = ([N ], [K]) with O ⊂ [N ] as the set of oblivious servers, let Di be the number of downloaded symbols for retrieving the ith message, i ∈ K, in the LPIR scheme, on the subgraph G′ = ([N ] \ O, K), where K = ∪n,m∈[N ]\O In ∩ Im . Further, let Di,n be the corresponding number of symbols downloaded from the nth server. If the vertices [N ] \ O are a vertex cover for G, and letting K′ = [K] \ K, the capacity is lower bounded by P
i Li
C≥
Γ
9
,
(19)
where Γ=
X
Di +
i∈K
X
X
n∈[N ]\O:Di,n
Lk
>0 k∈K′ ∩I
n
! +
X
X
X
i∈K′ n∈[N ]\O: ∃ℓ∈K with D
ℓ,n >0,{i,ℓ}⊆In
j∈K′ ∩I
Lj + Dℓ,n
.
(20)
n
Proof: The proof is based on a scheme where we apply the LPIR scheme on the new graph G = ([N ] \ O, K) when downloading θ ∈ K, in addition to downloading the extra messages in K′ if the server is contacted in the LPIR scheme when retrieving θ. In the case when θ = i ∈ K′ , we identify the unique server, n ∈ [N ] \ O, that stores the message Wi . From this server, we download Dℓ,n , i.e., the locally private scheme answer sent in response to θ = ℓ where ℓ ∈ K, alongside the clear messages indexed by In ∩ K′ . ■ In the next theorem, we define a notion of modified edge server privacy for general trees. In our context, a tree refers to any connected graph which has leaves, i.e., nodes whose degree is 1, and is not necessarily acyclic. Equivalently, we refer to the servers corresponding to the leaves as edge-servers, each of which stores a single message. Definition 5 (Modified edge-server privacy) Given a tree graph G, let L ⊂ [N ] denote the set of leaf nodes. Corresponding to a leaf node l ∈ L, let ϕ(l) be its unique parent node. Under local privacy with modified-edge server privacy, the privacy sets are given by I , n ∈ L, ϕ(n) Pn = (21) I n , n ∈ [N ] \ L. Remark 3 Note that the mapping ϕ : L → [N ] \ L is surjective, but not injective, since a parent node may have more than one leaf. Theorem 4 Let Dk be the download cost of a local PIR scheme ΠLP IR , associated with θ = k, and let Dk,n denote the corresponding download from server n. For a tree graph G under modified edge-server privacy of Definition 5, the capacity is lower bounded as C ≥ max P ΠLP IR
k∈[K] Dk +
KL P
n∈L
P
k∈Pn \{ℓ}: In ={ℓ} (Dℓ,n − Dk,n )
.
(22)
Proof: The achievability proof builds on any local PIR scheme, and modifies it to suit the modified privacy constraint. Note that, to preserve privacy, the user now downloads more from the servers in L, while the downloads from the remaining servers stay the same. Fix a local PIR scheme ΠLP IR . Let the answer from server n when θ = k for k ∈ Pn \ In incur the download cost of Dk,n . For θ = ℓ where In = {ℓ}, and n ∈ L, the number of downloaded 10
symbols from server n is Dℓ,n . In either case, the download is either ∅ or symbols of Wℓ only. For every n ∈ L, when k ∈ / In , the user queries for the same answers that it downloads from server n if θ = ℓ, where In = {ℓ}, which leads to the additional download cost. ■ Remark 4 If G is the star graph SN , where server N stores all the messages W and Wn = {Wn }, n ∈ [N − 1], then L = [N − 1] and ϕ(l) = N for all l ∈ L. As a result, the modified edge privacy setting reduces to the GPIR setting.
5
Results on Path Graphs
For a path graph on N nodes PN , the storage of server n is Wn = {Wn , Wn−1 }, n ∈ [2 : N −1], with edge-server storage W1 = {W1 } and WN = {WN −1 }. Theorem 5 (Path graphs with local privacy and modified edge-servers privacy) For the path graph PN with modified edge-servers privacy using Definition 5, i.e., the privacy sets are given by Pn = In , n ∈ [2 : N − 1], and P1 = P2 and PN = PN −1 , the capacity is C=
N −1 . 2N − 3
(23)
Remark 5 In comparison with the GPIR for PN , we note that for N ≥ 4, the capacity for the path graph with modified edge-servers privacy is higher than the capacity for the N −1 aforementioned setting, i.e., 2N > N2 [27]. −3 Remark 6 Since PN is a tree, from Theorem 4 the capacity for the modified edge-server setting is upper bounded by the LPIR capacity. In particular, compared to LPIR on PN , when N −1 N −1 N is odd1 , the capacity of LPIR is strictly higher, since CLP IR (PN ) = 2N > 2N [33]. −4 −3 Proof: For the upper bound, for θ = k, we bound the download cost Dk as, Dk ≥
N X
[k]
(24)
[k]
(25)
H(A[k] n |Q) ≥ H(A[N ] |Q)
n=1 [k]
= H(Wk |A[N ] , Q) + H(A[N ] |Q) [k]
= H(Wk |Q) + H(A[N ] |Wk , Q) [k]
= L + I(W \ {Wk }; A[N ] |Wk , Q). 1
(26) (27)
We compare with the odd number of servers, N , because the LPIR capacity is resolved in this case, unlike for the even number of servers case.
11
The proof relies on showing the following inequalities, [2] H(A2 |W1 , Q), [3] L 2 + H(A3 |W1 , W2 , Q), [k] [k+1] I(W \ {Wk }; A[N ] |Wk , Q) ≥ H(A[k−1] |Wk , Q) + H(Ak+1 |Wk , Q), k [N −3] L + H(AN −2 |WN −1 , WN −2 , Q), 2 [N −2] H(AN −1 |WN −1 , Q),
k=1 k=2 k ∈ [3 : N − 3] (28) k =N −2 k = N − 1.
Note that the second and fourth inequalities are introduced in this setting, while the others are the same as those in local PIR [32]. This is because the number of servers that queries for W2 and WN −2 require privacy from has increased, compared to that in local PIR. We show the proof of k = 2, and the case of k = N − 2 follows similarly, [2]
I(W \ {W2 };A[N ] |W2 , Q) [2]
[2]
[2]
≥ I(W1 , W3 ; A1 , A2 , A3 |W2 , Q) [2]
[2]
(29) [2]
≥ I(W1 ; A1 , A2 |W2 , Q) + I(W3 ; A3 |W1 , W2 , Q) (30) 1 1 [2] [2] [2] (31) ≥ I(W1 ; A1 |W2 , Q) + I(W1 ; A2 |W2 , Q) + I(W3 ; A3 |W1 , W2 , Q) 2 2 1 1 [3] [1] [1] = H(A1 |W2 , Q) + H(A2 |W2 , Q) + H(A3 |W1 , W2 , Q) (32) 2 2 1 1 [1] [1] [1] [1] [3] ≥ H(A1 , A2 |W2 , Q) + H(W1 |A1 , A2 , W2 , Q) + H(A3 |W1 , W2 , Q) (33) 2 2 L [3] = + H(A3 |W1 , W2 , Q), (34) 2 [2]
[2]
[2]
[2]
[2]
where (31) is due to 2I(W1 ; A1 , A2 |W2 , Q) = I(W1 ; A1 |W2 , Q) + I(W1 ; A2 |A1 , W2 , Q) + [2] [2] [2] I(W1 ; A2 |W2 , Q) + I(W1 ; A1 |A2 , W2 , Q), and (32) is due to privacy. Now, by summing (27) over all k, and using (28), we obtain, N −1 X
[2]
Dk − (N − 1)L ≥ H(A2 |W1 , Q) +
k=1
+
N −3 X
[k−1]
H(Ak
L [3] + H(A3 |W1 , W2 , Q) 2
[k+1] |Wk , Q) + H(Ak+1 |Wk , Wk−1 , Q)
k=3
L [N −3] [N −2] + + H(AN −2 |WN −1 , WN −2 , Q) + H(AN −1 |WN −1 , Q) 2 [2] [3] [2] = L + H(A2 |W1 , Q) + H(A3 |W1 , W2 , Q) + H(A3 |W3 , Q)
(35)
[N −4]
[4]
+ H(A4 |W3 , W2 , Q) + . . . + H(AN −3 |WN −3 , Q) [N −2]
[N −2]
+ H(AN −2 |WN −2 , WN −3 , Q) + H(AN −1 |WN −1 , Q)
12
(36)
[2] [2] ≥ L + H(A2 , A3 |W \ {W2 }, Q) +
N −2 X
[k]
[k]
H(Ak , Ak+1 |W \ {Wk }, Q)
k=3
(37) [2]
[2]
= L + H(W2 , A2 , A3 |W \ {W2 }, Q) +
N −2 X
[k]
[k]
H(Wk , Ak , Ak+1 |W \ {Wk }, Q)
(38)
k=3 [2]
[2]
= L + 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)
(39)
k=3
= (N − 2)L.
(40)
P −1 PN −1 Thus, (40) gives N k=1 Dk − (N − 1)L ≥ (N − 2)L, hence k=1 Dk ≥ (2N − 3)L. This gives the desired converse, PK
(N − 1)L (N − 1)L (N − 1) = PK ≤ = . (2N − 3)L (2N − 3) i=k Dk i=k Dk
k=1 R = PK
Lk
(41)
For achievability, we have two cases. The first case is θ ∈ {1, N − 1} and the second case is θ ∈ [2 : N − 2]. For each k ∈ [N − 1], let L = 2 for all messages, and let Wk (i) denote the ith symbol of Wk after permuting the indices of the messages uniformly at random. In the first case, we focus on θ = 1 and the other case is handled similarly. In this case, we download W1 (1) from server 1, W1 (2) + W2 (1) from server 2 and W2 (1) from server 3. For the second case, assume without loss of generality that θ = 2. Then, we download W1 (1) from server 1, W1 (1) + W2 (1) from server 2 and W2 (2) + W3 (1) from server 3 and W3 (1) from server 4. The total downloaded symbols is given by D = 2(3) + (N − 3)(4) = 2(2N − 3) and 2(N −1) N −1 the rate is given by R = 2(2N = 2N , concluding the achievability proof. ■ −3) −3 Theorem 6 (Path graphs with one-sided h-neighbor privacy) Given the path storage graph PN with one-sided h-neighbor privacy sets Pn = [max(1, n − 1) : min(n + h, N − 1)],
(42)
the capacity is lower bounded by C ≥ (h+2)(h+1) 2
2(N − 1) + 3h + 5 + (h + 4)(N − h − 3)
,
(43)
where h ∈ {1, . . . , N − 2}. Remark 7 When h = 0, this reduces to the local privacy setting, for which, we use the N −1 when N is even scheme for local PIR in [32, 33] where CLP IR (PN ) is lower bounded by 2N −3 13
N −1 and is equal to 2N when N is odd [32, 33]. Interestingly, since there is no value of h for −4 which the privacy sets cover all message indices, we do not recover the GPIR setting.
Remark 8 The main reason why the case h = 0 is not considered here is that the scheme for h = 0 is dependent on the bipartite graph structure of PN and requires downloading all messages in Wn whenever server n is contacted, for privacy. However, for h > 0, as the privacy sets become larger and non-symmetric, the bipartite scheme becomes less efficient. Proof: There are three cases in this setting. The first is when θ ∈ [1 : h + 1], in which case, we download (θ + 2) symbols from server 1 to server (θ + 2) as follows. If θ = 1, we download W1 (1) from server 1 and use it as an information symbol. From the second server, we download W1 (2) + W2 (1) and from the third server, we download W2 (1). If θ ̸= 1, we download W1 (1) to be used as side information. Further, we download Wθ−1 (1)+Wθ (1) from the θth server and Wθ (2) + Wθ+1 (1) from the (θ + 1)th server, Wθ+1 (1) from (θ + 2)th server and Wk−1 (1) + Wk (1) from the kth server, where k ∈ [2 : θ − 1]. The second case is when θ ∈ [h + 2 : N − 2], in which case, we download h + 4 symbols starting with server k − 1 when θ = h + k as a clean symbol for the largest index message, i.e., Wk (1), which acts as side information. Similarly, server k + h + 2 acts as a source of side information, where Wk+h+1 (1) is downloaded, and for the rest of the servers in between, we download Wm−1 (1) + Wm (1) for m ∈ [k : k + h + 1] \ {θ − 1, θ}, Wθ−1 (1) + Wθ (1) from the θth server and Wθ (2) + Wθ+1 (1) from the (θ + 1)th server. For the case when θ = N − 1, we download one symbol from the last h + 3 servers in a similar fashion. Thus, the sum of all downloaded symbols is given by N −1 X
Dθ =
h+1 X
! θ+2
+
θ=1
θ=1
=
N −2 X
! h+4
+h+3
(44)
θ=h+2
(h + 2)(h + 1) + 3h + 5 + (h + 4)(N − h − 3), 2
(45)
and the rate expression in (43) follows. ■ Theorem 7 (Path graphs with two-sided h-neighbor privacy) Given the path storage graph PN with two-sided h-neighbor privacy sets Pn = [max(1, n − h − 1) : min(n + h, N − 1)], the capacity is lower and upper bounded as 2(N −1) , 2(N − 1) (h+2)(2N −h−3)−(h+1)(h+2) ≤C≤ 2(N −1) (h + 2)(2N − h − 3)
, (h+2)(2N −h−3)−(N −h−1)(N −h−2)
where h ∈ {1, . . . , N − 3}.
14
0 ≤ h ≤ ⌈ N2−4 ⌉, ⌈ N2−4 ⌉ < h ≤ N − 3,
(46)
(47)
Remark 9 When h = 0, we recover the local privacy setting, and we obtain the same result as the first sentence of Remark 7. On the other hand, when h = N − 2, each privacy set is [K], yielding CP IR (PN ) = N2 . Proof: We start with the lower bound. For better exposition, we explain the scheme with reference to the GPIR scheme on the path graph given in [27]. Assume Li = 2 for all i ∈ [K]. Let θ = k. The set of servers Nk that have k in their privacy set is given by Nk = [max(1, k − h) : min(N, h + k + 1)].
(48)
We analyze this in two cases: Case 1: h ≤ ⌈ N2−4 ⌉. In this range, no message index appears in all Pn , n ∈ [N ]. This results in the following three ranges of k: 1. If k ∈ [h + 1], then Nk = [1 : h + k + 1]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk and server h + k + 2, when θ = k. 2. If k ∈ [h + 2 : N − h − 2], then Nk = [k − h : h + k + 1]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk , server k − h − 1 and server h + k + 2, when θ = k. 3. If k ∈ [N − h − 1 : N − 1], then Nk = [k − h : N ]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk and server k − h − 1, when θ = k. Let Mk = |Nk | + 1, c1,k = h + k + 2, c2,k = 2h + 4 and c3,k = N − k + h + 2. Then, 2(N − 1) PN −1 PN −h−2 k=1 Mk + k=h+2 (Mk + 1) + k=N −h−1 Mk 2(N − 1) = Ph+1 PN −h−2 PN −1 k=1 c1,k + k=h+2 c2,k + k=N −h−1 c3,k N −1 = Ph+1 k=1 (h + k + 2) + (h + 2)(N − 2h − 3) 2(N − 1) = . (h + 2)(2N − h − 3)
R = Ph+1
(49) (50) (51) (52)
Case 2: h > ⌈ N2−4 ⌉. In this range, there exists at least one k that is present in the privacy set of all servers. This results in the following three ranges of k: 1. If k ∈ [1 : N − h − 2], then Nk = [1 : h + k + 1]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk and server h + k + 2, when θ = k.
15
2. If k ∈ [N − h − 1 : h + 1], then Nk = [N ]. Download one symbol corresponding to the PIR scheme on path graph PN , when θ = k. 3. If k ∈ [h + 2 : N − 1], then Nk = [k − h : N ]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk and server k − h − 1, when θ = k. Then, R = PN −h−2
2(N − 1) Ph+1
(53)
PN −1 k=1 k=N −h−1 N + k=h+2 Mk 2(N − 1) = PN −h−2 Ph+1 PN −1 c + N + 1,k k=1 k=N −h−1 k=h+2 c3,k 2(N − 1) = PN −h−2 2 k=1 (h + k + 2) + (2h + 3 − N )N 2(N − 1) = . (h + 2)(2N − h − 3) Mk +
(54) (55) (56)
This concludes the proof of the lower bound in (47). For the upper bound, we start by lower bounding the download cost when θ = k as [k]
Dk ≥ L + I(W \ {Wk }; A[N ] |Wk , Q),
(57) [k]
and derive the following inequalities on the interference Tk = I(W \ {Wk }; A[N ] |Wk , Q) term. We analyze it in the same two ranges of h as the achievable scheme: Case 1: h ≤ ⌈ N2−4 ⌉. Then, if k ∈ [h + 1], k is present in the privacy sets of servers [h + k + 1]. For k = 1, [1]
(58)
[1]
(59)
[1]
(60)
[l]
(61)
H(Al |W1:l−1 , Q)
[l]
(62)
[l]
(63)
T1 ≥ I(W2:h+2 ; A[N ] |W1 , Q) =
h+2 X
I(Wl ; A[N ] |W1:l−1 , Q)
l=2
≥
=
= ≥
h+2 X l=2 h+2 X l=2 h+2 X l=2 h+2 X
I(Wl ; Al |W1:l−1 , Q) I(Wl ; Al |W1:l−1 , Q)
H(Al |W \ {Wl }, Q),
l=2
16
[l]
where the last equality holds since H(Al |W1:l , Q) = 0. For k ∈ [2 : h + 1], we have [k]
Tk ≥ I(W1:k−1 , Wk+1:h+k+1 ; A[N ] |Wk , Q)
(64)
[k]
[k]
(65)
[k]
(66)
= I(W1:k−1 ; A[N ] |Wk , Q) + I(Wk+1:h+k+1 ; A[N ] |W1:k , Q) ≥
k X
[k] I(Wl−1 ; Al |Wl:k , Q) +
l=2
=
k X
h+k+1 X l=k+1
[l−1] I(Wl−1 ; Al |Wl:k , Q) +
h+k+1 X
l=2
=
k X
≥
[l]
I(Wl ; Al |W1:l−1 , Q)
(67)
l=k+1 [l−1]
H(Al
|Wl:k , Q) +
l=2 k X
I(Wl ; Al |W1:l−1 , Q)
h+k+1 X
[l]
h(Al |W1:l−1 , Q)
(68)
l=k+1 [l−1] H(Al |W \ {Wl−1 }) +
l=2
h+k+1 X
[l]
H(Al |W \ {Wl }).
(69)
l=k+1
Next, for k ∈ [h + 2 : N − h − 2], Nk = [k − h : h + k + 1], and we similarly obtain Tk ≥
k X
[l−1] H(Al |W \ {Wl−1 }) +
h+k+1 X
[l]
H(Al |W \ {Wl }).
(70)
l=k+1
l=k−h
Similarly, for k ∈ [N −h−1 : N −1], we have Nk′ ∈ [k−h : N ], therefore for k ∈ [k−h : N −2], Tk ≥
k X
N −1 X
[l]
(71)
TN −1 ≥ I(WN −2−h:N −2 ; A[N ] |WN −1 , Q)
(72)
[l−1] H(Al |W \ {Wl−1 }) +
H(Al |W \ {Wl }).
l=k+1
l=k−h
For k = N − 1, by symmetry with k = 1, we have [N −1]
= ≥
= ≥
h+2 X l=2 h+2 X l=2 h+2 X l=2 h+2 X
[N −1]
(73)
[N −1]
(74)
[N −l]
(75)
I(WN −l ; A[N ] |WN −l+1:N −1 , Q) I(WN −l ; AN −l+1 |WN −l+1:N −1 , Q) I(WN −l ; AN −l+1 |WN −l+1:N −1 , Q) [N −l]
H(AN −l+1 |W \ {WN −l }, Q).
l=2
17
(76)
Now, summing over all k, and pairing the terms with the same superscript, we obtain N −1 X
Tk ≥ (h + 1)(N − h − 3)L.
(77)
Dk ≥ (N − 1)L + (h + 1)(N − h − 3)L
(78)
k=1
This yields N −1 X k=1
1 1 = (h + 2)(2N − h − 3)L − (h + 1)(h + 2)L, 2 2
(79)
and thus the upper bound in (47) for h ≤ ⌈ N2−4 ⌉ follows. Case 2: h > ⌈ N2−4 ⌉. For k ∈ [1 : N − h − 2], we similarly compute the bounds as Ph+2 H(A[l] |W \ {W }), k = 1, l l Tk ≥ Pkl=2 P [l] [l−1] |W \ {Wl−1 }) + h+k+1 l=k+1 H(Al |W \ {Wl }), k ∈ [2 : N − h − 2]. l=2 H(Al (80) For k ∈ [N − h − 1 : h + 1], Nk = [N ]. For these indices, the bound in standard GPIR holds, Dk ≥
N N −2 L=L+ L, 2 2
(81)
since the GPIR capacity for path graphs is N2 . For k ∈ [h + 2 : N − 1], we similarly have P −1 [l] [l−1] P k |W \ {Wl−1 }) + N l=k+1 H(Al |W \ {Wl }), k ∈ [h + 2 : N − 2], l=k−h H(Al Tk ≥ Ph+2 [N −l] k = N − 1. l=2 H(AN −l+1 |W \ {WN −l }, Q), (82) Summing across all k ∈ [N − 1], by grouping together answers with the same superscript, we obtain N −1 X k=1
Dk ≥ (N − 1)L +
NX −h−2
Tk +
k=1
N −1 X
Tk +
k=h+2
h+1 X
(N − 2) L 2 k=N −h−1
(N − 2)L 2 (h + 2)(2N − h − 3)L (N − h − 1)(N − h − 2)L = − , 2 2 = (N − 1)L + h(N − h − 2)L + (2h − N + 3)
which yields the upper bound for h > ⌈ N2−4 ⌉ in (47) . ■ 18
(83) (84) (85)
Theorem 8 (Path graphs with two-sided h-neighbor and modified edge-servers privacy) Consider the privacy sets for server n in PN given by Definition 5, i.e., P1 = P2 , PN = PN −1 , and Pn for n ∈ [2 : N − 1] as Pn = [max(1, n − h − 1) : min(n + h, N − 1)], the capacity is lower and upper bounded as 2(N −1) , 2(N − 1) ≤ C ≤ (h+2)(2N −h−3)−h(h+1) 2(N −1) (h + 2)(2N − h − 3)
, (h+2)(2N −h−3)−(N −h−4)(N −h−5)
0 ≤ h ≤ ⌈ N2−6 ⌉, ⌈ N2−6 ⌉ < h ≤ N − 3,
(86)
(87)
where h ∈ {0, 1, . . . , N − 3}. Remark 10 When h = 0, we recover the modified edge-servers privacy setting, as in Theorem 5, and the GPIR setting when h = N − 2. Proof: The basics of the scheme is the same as the one in Theorem 7, and the rate is derived similarly, with the following minor changes. The number of servers Nk′ that have k in their privacy sets is k = h + 2, Nh+2 ∪ {1}, Nk′ =
NN −h−2 ∪ {N }, k = N − h − 2, Nk , otherwise.
(88)
We analyze this in two cases: Case 1: h ≤ ⌈ N2−6 ⌉. In this range, no message index appears in all Pn , n ∈ [N ]. This results in the following three ranges of k: 1. If k ∈ [h + 2], then Nk′ = [1 : h + k + 1]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk′ and server h + k + 2, when θ = k. 2. If k ∈ [h + 3 : N − h − 3], then Nk′ = [k − h : h + k + 1]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk′ , server k − h − 1 and server h + k + 2, when θ = k. 3. If k ∈ [N − h − 2 : N − 1], then Nk′ = [k − h : N ]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk′ and server k − h − 1, when θ = k. This gives the same rate R=
2
2(N − 1) P PN −1 N −h−3 ′ ′ ′ M + 2M + 1 + k k k=1 k=h+3 k=N −h−1 Mk
Ph+1
19
(89)
2(N − 1) PN −h−2 PN −1 k=1 Mk + k=h+2 Mk + 1 + k=N −h−1 Mk 2(N − 1) = , (h + 2)(2N − h − 3) = Ph+1
(90) (91)
where Mk′ = |Nk′ | + 1. Case 2: h > ⌈ N2−6 ⌉. In this range, there exists at least one k that is present in the privacy set of all servers. This results in the following three ranges of k: 1. If k ∈ [1 : N − h − 3], then Nk′ = [1 : h + k + 1]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk′ and server h + k + 2, when θ = k. 2. If k ∈ [N − h − 2 : h + 2], then Nk′ = [N ]. Download one symbol corresponding to the PIR scheme on the path graph PN , when θ = k. 3. If k ∈ [h + 3 : N − 1], then Nk′ = [k − h : N ]. Download one symbol corresponding to the PIR scheme on the path graph consisting of Nk′ and server k − h − 1, when θ = k. R = PN −h−3 k=1
Mk′ +
= PN −h−3
2(N − 1) Ph+2
PN −1
(92)
2(N − 1) Ph+2
PN −1
(93)
k=N −h−2 N +
c1,k + k=N −h−2 N + 2(N − 1) = . (h + 2)(2N − h − 3) k=1
′ k=h+3 Mk
k=h+3 c3,k
(94)
This concludes the derivation of the lower bound in (87). For the upper bound, we proceed by starting from (57) and deriving the following in[k] equalities on the interference Tk = I(W \ {Wk }; A[N ] |Wk , Q) term. We analyze it in the same two ranges of h as in the achievable scheme: Case 1: h ≤ ⌈ N2−6 ⌉. If k ∈ [h+2], then k is present in the privacy sets of servers [h+k +1]. For k = 1, we obtain the same bound as in the first case of Theorem 7, i.e., T1 ≥
h+2 X
[l]
H(Al |W \ {Wl }, Q).
(95)
l=2
For k = 2, we obtain the bound [2] [2] T2 ≥ I(W1 ; A1 , A2 |W2 , Q) +
h+3 X
[2]
I(Wl ; Al |W1:l−1 , Q)
l=3 h+3 X
1 [1] [1] [l] ≥ I(W1 ; A1 , A2 |W2 , Q) + I(Wl ; Al |W1:l−1 , Q) 2 l=3 20
(96)
(97)
h+3 X 1 [1] [1] [l] = H(A1 , A2 |W2 , Q) + H(Al |W1:l−1 , Q) 2 l=3
(98)
h+3 X 1 [1] [1] [l] ≥ H(A1 , A2 |W \ {W1 }, Q) + H(Al |W \ Wl , Q) 2 l=3
(99)
h+3 L X [l] H(Al |W \ {Wl }, Q). = + 2 l=3
(100)
For k ∈ [3 : h + 2], we follow similar steps to obtain k h+k+1 X L X [l−1] [l] Tk ≥ + H(Al |W \ {Wl−1 }) + H(Al |W \ {Wl }). 2 l=3 l=k+1
(101)
Next, for k ∈ [h + 3 : N − h − 3], we have Tk ≥
k X
[l−1] H(Al |W \ {Wl−1 }) +
l=k−h
h+k+1 X
[l]
H(Al |W \ {Wl }).
(102)
l=k+1
Similarly, for k ∈ [k − h : N − 3], we have Tk ≥
k N −2 X X L [l−1] [l] + H(Al |W \ {Wl−1 }) + H(Al |W \ {Wl }). 2 l=k−h l=k+1
(103)
For k = N − 2, we have [N −2] [N −2] TN −2 ≥ I(WN −1 ; AN , AN −1 |WN −2 , Q) +
h+3 X
[N −2]
I(WN −l ; AN −l+1 |WN −1:N −l+1 , Q)
l=3 h+3 X
(104)
1 [N −1] [N −1] [N −1] ≥ I(WN −1 ; AN , AN −1 |WN −2 , Q) + I(WN −l ; AN −l+1 |WN −1:N −l+1 , Q) 2 l=3
(105)
h+3 X 1 [N −1] [N −1] [N −l] = H(AN , AN −1 |WN −2 , Q) + H(AN −l+1 |WN −1:N −l+1 , Q) 2 l=3
(106)
h+3 X 1 [N −1] [N −1] [N −l] ≥ H(AN , AN −1 |W \ {WN −1 }, Q) + H(AN −l+1 |W \ {WN −l }, Q) 2 l=3
(107)
h+3 L X [N −l] = + H(AN −l+1 |W \ {WN −l }, Q). 2 l=3
(108)
For k = N − 1, the bound is identical to that in the first case of Theorem 7, i.e., TN −1 ≥
h+2 X
[N −l]
H(AN −l+1 |W \ {WN −l }, Q).
l=2
21
(109)
Now, summing over all k, and pairing the terms with the same superscript, we obtain N −1 X
Tk ≥ (h + 1)L +
k=1
h+2 X
(l − 1)L +
l=2
NX −h−3
(h + 1)L +
N −2 X
(N − l − 1)L
(110)
l=N −h−2
l=h+3
= (h + 1)(N − h − 2)L.
(111)
This yields N −1 X
Dk ≥ (N − 1)L + (h + 1)(N − h − 2)L
(112)
k=1
1 1 = (h + 2)(2N − h − 3)L − h(h + 1)L, 2 2
(113)
and the upper bound in (87) for h ≤ ⌈ N2−6 ⌉ follows. Case 2: h > ⌈ N2−6 ⌉. For k ∈ [1 : N − h − 3], we have Ph+2 [l] k = 1, l=2PH(Al |W \ {Wl }), [l] Tk ≥ L2 + h+3 k = 2, l=3 H(Al |W \ {Wl }), P P [l] [l−1] h+k+1 k L + |W \ {Wl−1 }) + l=k+1 H(Al |W \ {Wl }), k ∈ [3 : N − h − 3]. l=3 H(Al 2 (114) For k ∈ [N − h − 2 : h + 2], Nk′ = [N ]. For these indices, the bound in standard GPIR holds Dk ≥
N N −2 L=L+ L, 2 2
(115)
since the GPIR capacity for path graphs is N2 . For k ∈ [h + 3 : N − 1], we similarly have Pk PN −2 [l−1] [l] L + H(A |W \ {W l−1 }) + l l=k−h l=k+1 H(Al |W \ {Wl }), k ∈ [h + 3 : N − 3], 2 P [N −l] Tk ≥ L2 + h+3 k = N − 2, l=3 H(AN −l+1 |W \ {WN −l }, Q), P h+2 H(A[N −l] |W \ {WN −l }, Q), k = N − 1. N −l+1 l=2 (116) Summing across all k ∈ [N − 1], by grouping together answers with the same superscript, we obtain N −1 X k=1
Dk ≥ (N − 1)L +
NX −h−3 k=1
N −1 X (N − 2) Tk + L+ Tk 2 k=N −h−2 k=h+3 h+2 X
= (h + 2)(2N − h − 3)L − (N − h − 4)(N − h − 5)L, 22
(117) (118)
and the upper bound in (87) for h ≥ ⌈ N2−6 ⌉ follows, concluding the proof. ■ Theorem 9 (Path graphs with local PIR and extremely private messages) Given a path storage graph PN with odd number of servers N , let E ⊂ [N − 1] be the set of message indices that are extremely private, then we have the following three capacity results: If neither 1 nor N − 1 are in E, then C=
2(N − 1) . (|E| + 4)N − 4|E| − 6
(119)
If exactly one of 1 or N − 1 are in E, then C=
2(N − 1) . (|E| + 4)N − 4|E| − 5
(120)
2(N − 1) . (|E| + 4)N − 4|E| − 4
(121)
If both 1 and N − 1 are in E, then C=
Proof: The achievability proof stems directly from applying the optimal scheme in [32, 33] for the messages in [N − 1] \ E and the optimal scheme for path graph GPIR in [22] for messages in E. The converse bound is given by Theorem 2. ■ Remark 11 For the even number of servers case in Theorem 9, the rates in (119), (120) and (121) are achievable. However, they do not yield capacity results since the optimal scheme for the even number of servers case for LPIR is so far unresolved. Theorem 10 (Path graphs with local PIR and oblivious edge-servers) Given the path storage graph PN with the first and last servers as oblivious, i.e., O = {1, N }, and the remaining servers follow local privacy, i.e., with privacy sets [N − 1], n ∈ {1, N }, Pn = (122) In , n ∈ {2, 3, . . . , N − 1}, the capacity is lower bounded by 1 C≥ , 2
(123)
with message lengths L1 = LN −1 = 1 and Li = 2 for i ∈ {2, 3, . . . , N − 2}. Proof: For any given θ, we download nothing from the two oblivious servers, and download two clear symbols from the servers where Wθ is replicated. Thus, we download 2 symbols in total if θ ∈ {1, N − 1}, and 4 symbols in total if θ ∈ [2 : N − 2], yielding the rate 12 . ■ 23
Remark 12 One can view Theorem 10 as a stricter version of modified edge-servers privacy for path storage graphs compared to Theorem 5. In Theorem 10, we consider them to be completely oblivious, whereas, in Theorem 5, we consider them to have the privacy set identical to that of their neighboring servers. Therefore, the capacity result in Theorem 5, N −1 serves as an upper bound for this setting. 2N −3 The following theorem is a capacity lower bound on PN where for any O ∈ [N ] such that [N ] \ O is a vertex cover of the graph and the remaining servers follow local privacy. Theorem 11 (Path graphs with non-oblivious servers forming a vertex cover) Given the path storage graph PN , if O is a subset of the odd-indexed servers and Pn = In for n ∈ [N ] \ O, then,
C≥
1, 2
N odd
N −1 ,
N even.
2N −3
If O is a subset of the even-indexed servers, then N −1 , N odd C ≥ 2N −4 N −1 , N even.
(124)
(125)
2N −3
In both cases, the length of each message is L = 1. Proof: Let V ⊆ [N ]\O be the minimal vertex cover for PN . For both cases, the achievability for θ = k holds by downloading all the messages from the specific server in the set V that stores Wθ , and nothing from the remaining servers. ■ Remark 13 It is clear that when N is odd and O is any subset of odd-indexed servers, the rate is the same as in Theorem 10. Thus, including servers in addition to the edge-servers in O does not affect the rate, even though the message lengths are different for the two schemes. In contrast, when N is odd and O is any subset of even-indexed servers, the scheme and the rate coincide with the optimal LPIR setting. Similarly, when N is even, the rate coincides with the best-known LPIR rate for both types of choices of O.
6
Results on Cyclic Graphs
For a cyclic graph on N nodes CN , the storage of server n is Wn = {Wn−1 , Wn } with the convention that W0 = WN .
24
Corollary 1 For any arbitrary privacy setting, the capacity of the cyclic graph with N = 3 servers is given by 1 C= . 2
(126)
The proof of Corollary 1 is a direct consequence of Lemma 1 where both the local PIR capacity and the GPIR capacity for C3 are equal to 12 . The GPIR scheme can be used without loss of generality for any arbitrary privacy. Although the GPIR scheme can be used for C3 for any arbitrary privacy, it requires the message subpacketization to be L = 8 symbols. This can be modified based on the specific arbitrary privacy requirement. As an example, in the case that the first server is oblivious and the other two servers require local privacy, the scheme in Table 5 shows that subpacketization with L = 2 symbols per message is possible.
θ=1 θ=2 θ=3
server 1 a1 , c1 a1 , c1 a1 , c1
server 2 a2 + b 1 a1 + b 1 b1
server 3 b1 b2 + c 1 c2 + b 1
Table 5: Scheme for C3 , where the first server is oblivious and the remaining two servers require local privacy.
Theorem 12 (Cyclic graph with 1st neighbor privacy) For the cyclic graph with N nodes CN with Pn = In ∪ In+1 , the capacity is lower and upper bounded as 1 2 ≤C≤ . 5 2
(127)
Remark 14 Note that both lower and upper bounds are independent of the number of servers N . This is because, the privacy for each index is confined to a fixed number of servers due to the symmetry of cyclic graphs unlike the path graphs. Remark 15 For N ≥ 5, the lower bound on the capacity with the 1st neighbor privacy is higher than the capacity of GPIR for the cyclic graph, where CP IR (CN ) = N2+1 [23]. Proof: For the lower bound, we proceed as follows. By the symmetry of CN , assume that θ = 1 without loss of generality. Let L = 2 symbols for all messages. The user permutes the message indices using permutations chosen uniformly at random. The user downloads W1 (1) + WN (1) from server 1 and W1 (2) + W2 (1) from server 2. To decode the two message symbols, the user downloads W2 (1) from server 3, WN (1) + WN −1 (1) from server N and WN −1 (1) from server N − 1. Thus, 5 symbols are downloaded to decode the required two message symbols.
25
For the upper bound, we have CLP IR (CN ) = 12 . Since the local PIR capacity is always higher than the arbitrary private set capacity, we have the upper bound. ■ Theorem 13 (Cyclic graph with ith neighbor privacy) For the cyclic graph with N nodes CN and Pn = In ∪ In+i , i ∈ [2 : N − 2], the capacity is bounded by, 2 1 ≤C≤ . 3 5
(128)
Remark 16 We have 25 here as an upper bound as opposed to a lower bound for Theorem 12. This is because the number of servers that have k ∈ Pn has increased for all k ∈ [K], requiring stricter privacy. Proof: To prove the lower bound, we proceed as follows. Without loss of generality, let θ = 1. From the first server, we download W1 (1) + WN (1). From the second server, we download W1 (2) + W2 (1). From the third server, we download W2 (1). To cancel the interference here, we have two cases, i = 2 and i > 2. If i = 2, we download WN (1)+WN −1 (1) from server N , WN −1 (1) + WN −2 (1) from server N − 1 and WN −2 (1) from server N − 2. If i > 2, we download WN (1) from server N and download any linear combination from any two servers other than the first and the second servers, that have 1 ∈ Pn . In all cases, we download 6 symbols to decode the 2 message symbols for any θ ∈ [N ], yielding the rate R = 2N = 13 . 6N For the upper bound, recall that [k]
Dk ≥ L + I(W \ Wk ; A[N ] |Wk , Q).
(129)
Let W ∗ = {Wk , Wk−1 , Wk−i+1 , Wk−i+3 , Wk+1 }, then, [k]
I(W \ Wk ; A[N ] |Wk , Q) [k]
[k]
≥I(Wk−i+1 , Wk−1 ; A[N ] |Wk , Q) + I(Wk−i+3 , Wk+1 ; A[N ] |Wk , Wk−1 , Wk−i+1 , Q) [k]
+ I(Wk−i−1 , Wk−i ; A[N ] |W ∗ , Q)
(130)
[k]
[k]
≥I(Wk−i+1 , Wk−1 ; Ak |Wk , Q) + I(Wk−i+3 , Wk+1 ; Ak+1 |Wk , Wk−1 , Wk−i+1 , Q) [k]
[k]
+ I(Wk−i−1 , Wk−i ; Ak−i , Ak−i+1 |W ∗ , Q) [k−1] [k+1] =H(Ak |Wk , Q) + H(Ak+1 |Wk , Wk−1 , Wk−i+1, , Q) [k] [k] + I(Wk−i−1 , Wk−i ; Ak−i , Ak−i+1 |W ∗ , Q).
(131)
(132)
Now, we prove that the third term in (132) is lower bounded by L2 . For convenience, we denote W ′ = {Wk−i−1 , Wk , Wk−1 , Wk−i+1 , Wk−i+3 , Wk+1 }. Thus, [k]
[k]
I(Wk−i−1 ,Wk−i ; Ak−i , Ak−i+1 |W ′ \ Wk−i−1 , Q) [k]
[k]
≥ I(Wk−i ; Ak−i , Ak−i+1 |W ′ , Q) 26
(133)
1 1 [k] [k] ≥ I(Wk−i ; Ak−i |W ′ , Q) + I(Wk−i ; Ak−i+1 |W ′ , Q) 2 2 1 1 [k−i] [k−i] = I(Wk−i ; Ak−i |W ′ , Q) + I(Wk−i ; Ak−i+1 |W ′ , Q) 2 2 1 1 [k−i] [k−i] = H(Ak−i |W ′ , Q) + H(Ak−i+1 |W ′ , Q) 2 2 1 1 [k−i] [k−i] ≥ H(Ak−i |W \ Wk−i , Q) + H(Ak−i+1 |W \ Wk−i , Q) 2 2 1 [k−i] [k−i] ≥ H(Ak−i , Ak−i+1 |W \ Wk−i , Q) 2 1 [k−i] [k−i] = H(Wk−i , Ak−i , Ak−i+1 |W \ Wk−i , Q) 2 L = . 2
(134) (135) (136) (137) (138) (139) (140)
Thus, summing over k ∈ [N ], we have N X
Dk ≥
k=1
≥
N 3N L X [k−1] [k+1] H(Ak |Wk , Q) + H(Ak+1 |Wk , Wk−1 , Wk−i+1, , Q) + 2 k=1
(141)
5N L , 2
(142)
where the last inequality follows the same way as in the proof of Theorem 5. ■ Theorem 14 (Cyclic graph with one-sided h-neighbor privacy) Consider the privacy sets for server n in CN given by Pn = [n − 1 : n + h],
(143)
where h ∈ {0, 1, . . . , N − 2}. The capacity is lower bounded as C≥
2 . h+4
(144)
Remark 17 The lower bound coincides with the PIR capacity, N2+1 when h = N −3, whereas Pn = [N ], n ∈ [N ] when h = N − 2. This gap suggests the existence of another scheme with 2 rate R = h+3 , which might be the capacity of this setting. Proof: Assume the message length is L = 2 and θ = k. Let the user independently permute the symbols of each message, uniformly at random, and denote the permuted message as Wk = [Wk (1), Wk (2)]. The set of servers Nk that have k in their privacy set is given by Nk = [k − h : k + 1].
(145)
From server ℓ ∈ [k − h : k], the user queries the sum Wℓ−1 (1) + Wℓ (1). From server k + 1, the user downloads the sum Wk (2) + Wk+1 (1). Now, from server k − h − 1, the user downloads 27
Wk−h−1 (1), and from server k+2, the user downloads Wk+1 (1) as interference symbols. These are used to cancel the unwanted message symbols and recover Wk . Thus, (h + 2) + 2 symbols 2 are downloaded to recover 2 symbols of Wk , resulting in the rate R = h+4 . ■ Theorem 15 (Cyclic graph with two-sided h-neighbor privacy) Consider the privacy sets for server n in CN given as Pn = [n − h − 1 : n + h],
(146)
where h ∈ {0, 1, . . . , ⌊ N2−3 ⌋}. The capacity is C=
1 . h+2
(147)
Remark 18 When h = 0, the capacity result coincides with that for LPIR since CLP IR (CN ) = 1 [32]. 2 Proof: To prove the achievability, let θ = 1. Then, the index needs to remain private from servers 3 to 2 + h on one side, and servers N to N − h + 1 on the other side, in addition to servers 1 and 2. From server 1, we download W1 (1)+WN (1), and from server 2, we download W1 (2) + W2 (1). From server k ∈ [3 : 2 + h], we download Wk−1 (1) + Wk (1), and similar downloads are made from server k ∈ [N − h + 1 : N ]. Then, from server 3 + h, we download 2N 1 W2+h (1) and the same goes for server N − h. Thus, the rate is R = 2(h+2)N = h+2 . To prove the converse, we have, as (27), for any k ∈ [N ], that Dk ≥ L + I(W \ [k] {Wk }; A[N ] |Wk , Q). Let W ′′ = {Wk−h−1 , . . . , Wk−1 , Wk+1 , . . . , Wk+h+1 }, then [k]
[k]
I(W \ {Wk }; A[N ] |Wk , Q) ≥ I(W ′′ ; A[N ] |Wk , Q) =
k X
[k]
I(Wl−1 ; A[N ] |W[l:k] , Q) +
≥
[k] I(Wl−1 ; Al |W \ {Wl−1 }, Q) +
=
k+h+1 X
[l−1] I(Wl−1 ; Al |W \ {Wl−1 }, Q) +
=
[k]
I(Wl ; Al |W \ {Wl }, Q)
k+h+1 X
(150)
[l]
I(Wl ; Al |W \ {Wl }, Q)
(151)
[l]
(152)
l=k+1
l=k−h k X
(149)
l=k+1
l=k−h k X
[k]
I(Wl ; A[N ] |W[k−h−1:l−1] , Q)
l=k+1
l=k−h k X
k+h+1 X
(148)
[l−1]
H(Al
|W \ {Wl−1 }, Q) +
k+h+1 X
H(Al |W \ {Wl }, Q).
l=k+1
l=k−h
Then, by summing over all k ∈ [N ], N X k=1
Dk − N L ≥
N X k X
[l−1] H(Al |W \ {Wl−1 }, Q) +
k=1 l=k−h
N k+h+1 X X k=1 l=k+1
28
[l]
H(Al |W \ {Wl }, Q) (153)
= (h + 1) ≥ (h + 1)
N X l=1 N X
[l] H(Al |W \ {Wl }, Q) + (h + 1)
N X
[l]
H(Al+1 |W \ {Wl }, Q) (154)
l=1 [l]
[l]
H(Al , Al+1 |W \ {Wl }, Q)
(155)
l=1
= (h + 1)N L, which gives
(156)
PN
k=1 Dk ≥ (h + 2)N L, thus completing the proof.
■
Theorem 16 (Cyclic graphs with local PIR and extremely private messages) Given a cyclic storage graph CN , let E ⊂ [N ], be the message indices that are extremely private, while the remaining indices follow local privacy. Then, the capacity is given by C=
2N (|E| + 4)N − 3|E|
(157)
Proof: Let |E| = n, we choose L = 4 N2 as the number of message symbols, and apply the scheme for cyclic graphs CN proposed in [23], to all or the pair of servers k and k + 1, depending on whether the desired message index k is extremely private or not, respectively. For k ∈ E, we apply the said scheme exactly to all servers. This involves N2 N2 (N + 1) downloaded symbols per server. If k ∈ / E, then we apply the said scheme only to the servers k and k + 1 and download the useful side information symbols from the servers k − 1 and k +2. Since the scheme in [23] requires the user to download N −1+2 N2 − (N − 1) 2-sum symbols from each server, we download the corresponding 2 N − 1 + 2 N2 − (N − 1) clear symbols from servers k − 1 and k + 2, to remove the interfering message symbols from the downloaded 2-sums. Thus, the total download is N X
N N 2 N Dk = 2n (N + 1) + 2(N − n) N − 1 + 2 − (N − 1) + (N + 1) . N 2 2 2 k=1 (158)
Thus, the rate is given by R=
=
4N N2
2n(N + 1) N2 + 2(N − n) N − 1 + 2
N 2
− (N − 1) + N2 N2 (N + 1)
(159)
4N · N (N2−1) N (N −1) N (N −1) 2 N (N −1) 2n(N + 1) 2 + 2(N − n) N − 1 + 2 − (N − 1) + N 2 (N + 1) 2
(160) =
2N 2 (N − 1) nN (N − 1)(N + 1) + 2(N − n) (N − 1 + (N − 1)(N − 2) + (N − 1)(N + 1)) 29
(161)
=
2N 2 (N − 1) nN (N − 1)(N + 1) + 2(N − n) · 2N (N − 1)
(162)
=
2N 2 (N − 1) N (N − 1) (n(N + 1) + 4(N − n))
(163)
=
2N 2 (N − 1) N (N − 1) (nN + n + 4N − 4n)
(164)
2N 2 (N − 1) N (N − 1) (nN + 4N − 3n) 2N 2N = . = nN + 4N − 3n (n + 4)N − 3n =
(165) (166)
To prove the converse bound, we use the converse bounds for cyclic graphs, from [33] and [23], in addition to Theorem 2. From [23], we know that Dk ≥
L (N + 1), 2
(167)
for all k ∈ E, from the symmetry of the graph and the privacy requirement. In addition, from [33], we have Dk ≥ 2L,
(168)
for k ∈ [N ] \ E, again from the symmetry of the graph and the privacy requirement. Then, by adding both together, we have N X
Dk =
n X
Dk +
Dk
(169)
k=n+1
k=1
k=1
N X
nL (N + 1) + 2(N − n)L 2 n 3 = NL + 2 − nL, 2 2
≥
(170) (171)
and the rate is upper bounded by NL 2N R= P ≤ , N (n + 4) − 3n k Dk
(172)
completing the capacity proof. ■ Remark 19 When n = N in Theorem 16, we recover the GPIR capacity of the cyclic graph [23]. In addition, when n = 0, we recover the LPIR capacity of the cyclic graph [33]. Theorem 17 (Cyclic graphs with non-oblivious servers forming a vertex cover) Let O ⊂ [N ] be the set of oblivious servers in CN and the remaining servers [N ] \ O follow local 30
privacy. If [N ] \ O forms a vertex cover for CN , the capacity is given by 1 C= , 2
(173)
Proof: Let V ⊆ [N ] \ O be fixed as the minimal vertex cover for CN . Then, each message is present in at least one server in V. We set the message lengths to be 2 for the messages that are stored at servers that are both in V, and the message lengths of the remaining messages as 1. Let θ = k. We have the following two cases. In the first case, both the messages stored at the server in V storing Wk are present in exactly one server in V. For all such k, we download both the messages from the server in V that stores Wk . In the second case, one of the messages stored at the server in V storing Wk is present in both servers in V. This has two sub-cases. First, if Wk is replicated in servers in V, i.e., servers {k, k + 1} ⊆ V. Then, we download Wk−1 and Wk+1 , from server k and server k + 1, respectively, in addition to downloading one distinct symbol of Wk from each of these servers. Second, if only one of the servers storing Wk is in V, we download Wk from this server, and a single symbol of the other message. For each case, we download double the number of desired message symbols, resulting in the rate 12 . The upper bound comes from the one for the LPIR setting, since the privacy constraints are more strict in this setting, compared to LPIR. One can check that the converse proof in [33] holds in this case with a slight modification to account for the unequal message lengths, yielding the same bound 12 . ■ Remark 20 Similar to Theorem 11 for PN , Theorem 17 is a refinement of the general case in Theorem 3, specific to CN . Different from Theorem 3, which may need to download from all servers in [N ] \ O that form a vertex cover (depending on the underlying LPIR scheme), Theorem 17 downloads only from the servers that form a minimal vertex cover. The following corollaries consider the case where [N ] \ O is the minimal vertex cover V for CN . We only show the achievability, since the upper bound proof is same as that of Theorem 17. Corollary 2 Given the cyclic storage graph with N servers, where N is even. Let the privacy sets be defined as follows I , n is even, n Pn = (174) [N ], n is odd, i.e., all the odd-indexed servers are oblivious. Then, the capacity is given by 1 C= . 2 31
(175)
Proof: Let Li = 1 for all i ∈ [N ]. Clearly, V is the set of all even-indexed servers. The scheme follows the first case of the proof of Theorem 17 for all desired indices. In particular, if θ = k, we download both the messages from the server in V with Wk in its storage and nothing from any other server. ■ Corollary 3 Given the cyclic storage graph with N servers, where N is odd. Let the privacy sets be defined as follows I , n ∈ {2, 4, 6, . . . , N − 1, N }, n Pn = (176) [N ], otherwise, i.e., all the odd-indexed servers except the N th server are oblivious. Then, the capacity is given by 1 C= . 2
(177)
Proof: Let LN −1 = 2 and Li = 1 for all i ∈ [N ] \ {N − 1}. Here, V = {2, 4, 6, . . . , N − 1, N }. We follow the same scheme as in Corollary 2, except when retrieving θ = N − 1, since it is available in servers N − 1 and N , both of which are in V. We download Wθ−1 , Wθ (1) from the (N − 1)st server and Wθ (2), Wθ+1 from the N th server after permuting the symbols of WN −1 uniformly at random. Thus, the rate is given by R=
(N − 1) + 2 1 = , 2(N − 1) + 4 2
(178)
giving the desired result. ■ Remark 21 Based on Corollary 2, we can see that, in this setting, we do not need to store messages in the oblivious servers. These servers are not contacted during the retrieval process, thus, their storage can be completely eliminated, saving storage space for the servers, without affecting the rate. In the next theorem, we generalize this result to the case where [N ] \ O is not necessarily a vertex cover. Theorem 18 (Cyclic graphs with local PIR and oblivious servers) Given a cyclic storage graph CN with O ⊂ [N ] being the set of oblivious servers. Then the capacity is lower bounded as P / IO ) + 21(k ∈ IL , k ∈ IO′ ) + 1(k ∈ IL , k ∈ IO\O′ ) + 1(k ∈ IO , k ∈ / IL ) k∈[N ] 21(k ∈ IL , k ∈ P P P C≥ , 2N |O′ | + 4 k 1(k ∈ IL , k ∈ / IO ) + 2 k 1(k ∈ IL , k ∈ IO′ ) + 2 k 1(k ∈ IL , k ∈ IO\O′ ) (179)
32
where L = [N ] \ O is the set of servers that follow local privacy, O′ is the minimal noncontiguous subset of O which makes V = L ∪ O′ a vertex cover; the message lengths are set as 2 symbols except for the message indices in IO\O′ which have message lengths equal to 1. Proof: If Wθ is present in two servers, such that both of them are in L, we download 2 clear symbols from each of the two servers with the required message as one of them. To ensure privacy, we additionally download 2 symbols from the oblivious servers in O′ , one each of the stored messages. Thus, we retrieve 2 symbols of Wθ by downloading 4 + 2|O′ | symbols. In the case when Wθ is present in one server in L, and one of the oblivious servers in O′ , we download the same way as in the previous setting. Thus, we get 2 symbols of useful information but only with 2 + 2|O′ | symbols downloaded. If Wθ is in one of the oblivious servers in O and one of the oblivious servers in O \ O′ , we download 2 clear symbols from the server in O′ with one of them being the required message. Thus, the number of downloaded symbols in this case is 2|O′ |. Finally, if Wθ is in one of the servers in L, and one of the servers in O \ O′ , we download 2 clear symbols from the server in L storing the message and to ensure privacy, we download two symbols from each server in O′ . ■ To demonstrate the statement of Theorem 18 with a specific setting, we provide the following example for C6 . Example 5 Consider C6 . Let the servers 1, 4, 5 and 6 be oblivious. We choose O′ = {1, 5}. Thus, L1 = L2 = 2 and Li = 1 for i ∈ [3 : 6]. Table 6 shows the retrieval scheme. The rate of the scheme is 41 . θ=1 θ=2 θ=3 θ=4 θ=5 θ=6
server 1 W1 (1), W6 W1 (1), W6 W1 (1), W6 W1 (1), W6 W1 (1), W6 W1 (1), W6
server 2 W1 (2), W2 (1) W1 (2), W2 (1)
server 3 W2 (2), W3 W2 (2), W3
server 4
server 5 W4 , W5 W4 , W5 W4 , W5 W4 , W5 W4 , W5 W4 , W5
server 6
Table 6: Scheme for C6 with O = {1, 4, 5, 6} and O′ = {1, 5} for Example 5.
7
The Pyramid Storage Graph
In this section, we introduce an interesting graph structure that has never been investigated in the PIR literature. The graph is a non-uniform hypergraph with N nodes and K = ⌊ N2 ⌋+3 messages, since each hyper-edge consists of unequal number of vertices. In the equivalent PIR system, the replication factor2 of messages ranges from ⌈N/2⌉ to ⌈N/2⌉ + 2. We name it the pyramid storage scheme and define it as follows. 2
For simple graphs, such as path and cycle graphs, the replication factor is 2, since each edge consists of two distinct vertices.
33
Definition 6 The pyramid storage graph is defined as follows for i ∈ [N ], Wi = W[max(1,i−⌈ N ⌉+1):min(i+2,⌊ N ⌋+3)] . 2
2
Thus, if the number of servers N is even, then the storage is given by {W , W , . . . , W } if 1 ≤ i ≤ N2 , 1 2 i+2 Wi = {W N , W N , . . . , W N } if N + 1 ≤ i ≤ N, i− 2 +1
i− 2 +2
+3 2
{W1 , . . . , Wt+3 } {Wi−t , . . . , Wt+3 },
(181)
2
and if the number of servers is odd, then the storage is given by if 1 ≤ i ≤ t, {W1 , . . . , Wi+2 }, Wi =
(180)
if i = t + 1,
(182)
if t + 2 ≤ i ≤ 2t + 1,
where N = 2t + 1. Definition 7 (Replication pattern) The replication pattern for the kth message Rk is the set of servers that stores Wk , Rk = {n ∈ [N ] : Wk ∈ Wn }.
(183)
Remark 22 The replication pattern for arbitrary N can be given by {1, 2, . . . , ⌈ N2 ⌉}, N {1, 2, . . . , ⌈ 2 ⌉ + 1} Rk = {k − 2, k − 1, . . . , ⌈ N2 ⌉ + k − 1}, {⌊ N2 ⌋, ⌊ N2 ⌋ + 1, . . . , N } N {⌊ 2 ⌋ + 1, ⌊ N2 ⌋ + 2, . . . , N },
if k = 1, if k = 2, if 3 ≤ k ≤ ⌊ N2 ⌋ + 1,
(184)
if k = ⌊ N2 ⌋ + 2, if k = ⌊ N2 ⌋ + 3.
For this graph, we present a scheme for local privacy that automatically ensures modified edge privacy (P1 = P2 and PN = PN −1 ), as outlined in the following theorem. Theorem 19 (Pyramid graph with modified edge-servers privacy) Given the pyramid storage graph in Definition 6 with the privacy sets P1 = P2 , PN = PN −1 , and Pk = Ik , k ∈ [2 : N − 1]. The message lengths are given by Li = |Ri |. Then, if N is even, the capacity has lower bounded as C≥
N 2 + 10N t2 + 5t = , 2(N 2 + 10N + 8) 2t2 + 10t + 4
34
(185)
where N = 2t. The capacity is lower bounded for odd N as C≥
t2 + 6t + 3 , 2t2 + 11t + 9
(186)
where N = 2t + 1. Prior to proving Theorem 19, we provide an example for the retrieval scheme for the case where the number of servers N is even. The odd number of servers case follows the same scheme. Example 6 (Pyramid storage for N = 6 servers) The storage for this case is given by W1 = {W1 , W2 , W3 }
(187)
W2 = {W1 , W2 , W3 , W4 }
(188)
W3 = {W1 , W2 , W3 , W4 , W5 }
(189)
W4 = {W2 , W3 , W4 , W5 , W6 }
(190)
W5 = {W3 , W4 , W5 , W6 }
(191)
W6 = {W4 , W5 , W6 }.
(192)
We represent the messages after permuting their symbol indices uniformly at random as W1 = [a1 , a2 , a3 ], W2 = [b1 , b2 , b3 , b4 ], W3 = [c1 , c2 , c3 , c4 , c5 ], W4 = [d1 , d2 , d3 , d4 , d5 ], W5 = 6 [e1 , e2 , e3 , e4 ] and W6 = [f1 , f2 , f3 ]. Table 7 provides the retrieval scheme. The rate is R = 13 . θ=1
server 1 a1 , b1 , c1
θ=2
a1 , b1 , c1
θ=3
a1 , b1 , c1
θ=4
a1 , b1 , c1
θ=5 θ=6
server 2 a2 + b1 + c1 + d 1 b2 + a1 + c1 + d 1 c2 + a 1 + b1 + d 1 d1 + a1 + b1 + c 1 a1 , b1 , c1
server 3 a3 + b 1 + c1 + d1 + e1 b3 + a 1 + c1 + d1 + e1 c3 + a 1 + b1 + d 1 + e 1 d2 + a 1 + b1 + c1 + e1 e1 + a 1 + b1 + c 1 + d 1 b1 , c1
server 4 d1 , e1
server 5
b4 + c1 + d1 + e1 + f1 c4 + b1 + d1 + e1 + f1 d3 + b1 + c1 + e 1 + f 1 e2 + b1 + c1 + d1 + f1 f1 + b 1 + c1 + d1 + e1
d1 , e1 , f1 c5 + d1 + e1 + f 1 d4 + c1 + e1 + f 1 e3 + c 1 + d1 + f 1 f2 + c1 + d1 + e 1
server 6
d1 , e1 , f1 d5 , e1 , f1 d1 , e4 , f1 f3 , d1 , e1
Table 7: The retrieval scheme for the pyramid storage graph for N = 6 in Example 6.
Proof: The achievable schemes for the even and the odd number of servers cases are similar, but the calculations are slightly different.
35
Prior to delving into the scheme for the even number of servers case, we calculate It is straightforward to check using Rk , that X
Lk = 2
k
N 2
+2
N N N +1 + −1 +2 2 2 2
N 2 5N = + . 4 2
P
Li .
(193) (194)
We initiate the scheme after permuting the indices of the messages independently and uniformly at random. If θ ∈ [4], we follow the following three steps: 1. Download 3 clear symbols from the first server, one from each message, i.e., W1 (1), W2 (1), W3 (1). 2. If θ ∈ Wn , where Wn = {Wθ , Wi1 , Wi2 , . . . , Wim }, download the (m + 1)-sum as follows Wθ (
X
1(θ ∈ Wm )) + Wi1 (1) + Wi2 (1) + . . . + Wim (1).
(195)
m∈[n]
3. Otherwise, if θ ∈ / Wn , then we download Wij (1) if Wij ∈ Wk and Wθ ∈ Wk , if not downloaded previously. If N ≥ 12 and θ ∈ [5 : N2 − 1], we only carry out steps 2 and 3 from the previous case. Finally, if θ ∈ [ N2 : N2 + 3], we change step 1 to downloading 3 clear symbols from the last server, one from each message, i.e., W N +1 (1), W N +2 (1), W N +3 (1) if θ = N2 , 2 2 2 W N +1 (|R N +1 |), W N +2 (1), W N +3 (1) if θ = N2 + 1, W N +1 (1), W N +2 (|R N +2 |), W N +3 (1) if θ = 2 2 2 2 2 2 2 2 N N N N N N + 2 and W + 3. (1), W (1), W (|R |) if θ = +1 +2 +3 +3 2 2 2 2 2 2 The number of downloaded symbols is given by N N + 1, θ ∈ {1, 2 + 3}, Dk =
N + 3, θ ∈ {2, N2 + 2}, N + 4, otherwise.
(196)
P 2 Thus, k Dk = N2 + 5N + 4, which concludes the proof for the even number of servers case. For the case of the odd number of servers, we follow the same scheme as the even number of servers. Note that the replication pattern for this case is given by {1, 2, . . . , t + 1}, {1, 2, . . . , t + 2} Rk = {k − 2, k − 1, . . . , t + k}, {t, t + 1, . . . , N } {t + 1, t + 2 . . . , N }, 36
if k = 1, if k = 2, if 3 ≤ k ≤ t + 1, if k = t + 2, if k = t + 3,
(197)
P P where N = 2t + 1. The sum of all message lengths is k Lk = t2 + 6t + 3 and k Dk = 2t2 + 11t + 9, yielding the lower bound and concluding the proof. ■ Remark 23 One can verify that the aforementioned scheme also works for the case with local privacy without any edge-servers privacy modifications. In addition, the scheme can be slightly modified by moving the side information downloaded from some servers to ensure the privacy in the following case P1 = P3 , PN = PN −2 , and Pn = In otherwise. In both cases, the rate is exactly the same.
8
Conclusion and Future Work
In this paper, we formulated the PIR problem with arbitrary privacy patterns for graphbased storage systems. In our problem formulation, for a given graph-replicated storage setting, its local PIR (LPIR) capacity and graph PIR (GPIR) capacity provide trivial upper and lower bounds, respectively, on the capacity for any arbitrary privacy setting. We derived general capacity bounds for all graphs for well-motivated privacy requirements that combine local privacy with stricter privacy requirements. To make the problem formulation tractable, we fixed the storage to simple graphs, specifically the path and the cyclic storage graphs. For these cases, we derived capacity bounds or exact capacity results for privacy sets that can be defined by the message indices contained in the storage of the neighboring servers. Specifically, we derived the exact capacity for the modified edge-servers privacy setting for path graphs. Moreover, the two-sided h-neighbor privacy setting demonstrates a unifying framework to move between the LPIR and GPIR settings, through the integer h. Next, we fine-tuned the general results of privacy settings with extremely private message subsets, and obtained capacity results for path graphs with odd numbers of vertices, and for cyclic graphs. Similarly, we derived capacity lower bounds and exact capacity for settings containing subsets of oblivious servers. Interestingly, for cyclic graphs with certain subsets of oblivious servers, we designed schemes with unequal message lengths such that the capacity remains the same as that of LPIR, even though the privacy settings are stricter. We then introduced the pyramid storage scheme and provided rate lower bounds for three specific privacy patterns. We believe that our paper serves as an initial stepping stone and opens up many new directions for future work. Beyond the privacy settings that we explored, one may construct other interesting, well-motivated privacy settings that reflect those that are encountered in practice. Although the LPIR capacity forms a trivial upper bound, finding a general framework to derive upper bounds, not necessarily tight, is an important open problem. Also, analyzing the asymptotic capacity as the number of servers N or the number of messages K grows to infinity is an interesting research direction.
37
References [1] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval. Jour. of the ACM, 45(6):965–981, November 1998. [2] H. Sun and S. Jafar. The capacity of private information retrieval. IEEE Trans. Info. Theory, 63(7):4075–4088, July 2017. [3] J. Cheng, N. Liu, W. Kang, and Y. Li. The capacity of symmetric private information retrieval under arbitrary collusion and eavesdropping patterns. IEEE Trans. Info. Foren. Security, 17:3037–3050, August 2022. [4] K. Banawan and S. Ulukus. Private information retrieval through wiretap channel II: Privacy meets security. IEEE Trans. Info. Theory, 66(7):4129–4149, February 2020. [5] K. Banawan and S. Ulukus. The capacity of private information retrieval from Byzantine and colluding databases. IEEE Trans. Info. Theory, 65(2):1206–1219, September 2018. [6] S. Vithana, K. Banawan, and S. Ulukus. Semantic private information retrieval. IEEE Trans. Info. Theory, 68(4):2635–2652, December 2021. [7] M. Nomeir, A. Aytekin, and S. Ulukus. The capacity of semantic private information retrieval with colluding servers. In IEEE Globecom, December 2025. [8] M. Nomeir, A. Aytekin, and S. Ulukus. The asymptotic capacity of Byzantine symmetric private information retrieval and its consequences. In IEEE ISIT, June 2025. [9] S. Ulukus, S. Avestimehr, M. Gastpar, S. Jafar, R. Tandon, and C. Tian. Private retrieval, computing, and learning: Recent progress and future challenges. IEEE J. Sel. Areas Commun., 40(3):729–748, March 2022. [10] Z. Jia, H. Sun, and S. Jafar. Cross subspace alignment and the asymptotic capacity of X-secure T -private information retrieval. IEEE Trans. Info. Theory, 65(9):5783–5798, May 2019. [11] Q. Wang, H. Sun, and M. Skoglund. The capacity of private information retrieval with eavesdroppers. IEEE Trans. Info. Theory, 65(5):3198–3214, December 2018. [12] Q. Wang and M. Skoglund. Symmetric private information retrieval from MDS coded distributed storage with non-colluding and colluding servers. IEEE Trans. Info. Theory, 65(8):5160–5175, March 2019. [13] M. Nomeir, S. Vithana, and S. Ulukus. Asymmetric X-secure T -private information retrieval: More databases is not always better. In CISS, March 2024.
38
[14] A. Aytekin, M. Nomeir, S. Vithana, and S. Ulukus. Quantum symmetric private information retrieval with secure storage and eavesdroppers. In IEEE Globecom, December 2023. [15] Y. Lu and S. Jafar. Quantum X-secure T-private information retrieval from MDS coded storage with unresponsive and Byzantine servers. IEEE J. Sel. Areas Info. Theory, 6:59– 73, 2025. [16] M. Nomeir, A. Aytekin, and S. Ulukus. Byzantine-eavesdropper alliance: How to achieve symmetric privacy in quantum X-secure B-Byzantine E-eavesdropped U -unresponsive T -colluding PIR? IEEE Trans. Info. Theory, 2025. [17] S. Song and M. Hayashi. Capacity of quantum private information retrieval with multiple servers. IEEE Trans. Info. Theory, 67(1):452–463, September 2021. [18] K. Banawan and S. Ulukus. The capacity of private information retrieval from coded databases. IEEE Trans. Info. Theory, 64(3):1945–1956, January 2018. [19] H. Sun and C. Tian. Breaking the MDS-PIR capacity barrier via joint storage coding. Information, 10(9):2078–2489, August 2019. [20] H. Lin, S. Kumar, E. Rosnes, A. i Amat, and E. Yaakobi. Multi-server weakly-private information retrieval. IEEE Trans. Info. Theory, 68(2):1197–1219, 2021. [21] C. Qian, R. Zhou, C. Tian, and T. Liu. Improved weakly private information retrieval codes. In IEEE ISIT, pages 2827–2832, 2022. [22] N. Raviv, I. Tamo, and E. Yaakobi. Private information retrieval in graph-based replication systems. IEEE Trans. Info. Theory, 66(6):3590–3602, November 2019. [23] K. Banawan and S. Ulukus. Private information retrieval from non-replicated databases. In IEEE ISIT, July 2019. [24] S. Keramaati and S. Salehkalaibar. Private information retrieval from non-replicated databases with optimal message size. In IWCIT, pages 1–6, 2020. [25] B. Sadeh, Y. Gu, and I. Tamo. Bounds on the capacity of private information retrieval over graphs. IEEE Trans. Info. Foren. Security, 18:261–273, November 2023. [26] Z. Jia and S. Jafar. On the asymptotic capacity of X-secure T-private information retrieval with graph-based replicated storage. IEEE Trans. Info. Theory, 66(10):6280– 6296, July 2020. [27] X. Kong, S. Meel, T. Maranzatto, I. Tamo, and S. Ulukus. New capacity bounds for PIR on graph and multigraph-based replicated storage. IEEE Trans. Info. Theory, 72(1):691–709, January 2026. 39
[28] S. Meel and S. Ulukus. The role of common randomness replication in symmetric PIR on graph-based replicated systems. IEEE Trans. Inf. Theory. To appear, also available online at arXiv:2602.16700. [29] G. Ge, H. Wang, Z. Xu, and Y. Zhang. Private information retrieval over graphs, 2025. Available online at arXiv:2509.26512. [30] V. Shanbhag and P. Krishnan. Private information retrieval for graph-based replication with minimal subpacketization, 2026. Available online at arXiv:2601.09957. [31] S. Meel and S. Ulukus. Effect of full common randomness replication in symmetric PIR on graph-based replicated systems. In IEEE ICC, May 2026. [32] S. Meel, M. Nomeir, and S. Ulukus. Local private information retrieval: A new privacy perspective for graph-based replicated systems. In IEEE ITW, 2026. To appear, also Available online at arXiv:2605.10872. [33] S. Meel, M. Nomeir, and S. Ulukus. Local private information retrieval for graph-based replicated systems, 2026. Available online at arXiv:2608.31150.
40