arXiv CS open access

Local Private Information Retrieval for Graph-Based Replicated Systems

2026 · arxiv_cs

arXiv CS · Papers · 2026

cryptography cybersecurity privacy security

Conceptio Open Archive

Analyze & explore related research in Conceptio

Connect this record directly into your research workflow or AI agent. Explore citations across open repositories, query full text, and export structured proof bundles.

Explore in Search →Connect via MCP / API ↗

Local Private Information Retrieval for Graph-Based Replicated Systems∗ Shreya Meel

Mohamed Nomeir

Sennur Ulukus

arXiv:2608.31150v1 [cs.IT] 31 Aug 2026

Department of Electrical and Computer Engineering University of Maryland, College Park, MD 20742 smeel@umd.edu mnomeir@umd.edu ulukus@umd.edu Abstract We rethink the deﬁnition of privacy in multi-server, graph-replicated private information retrieval (PIR) systems, by introducing a novel setting where the user’s privacy is governed by the servers’ storage structure. In classical graph-replicated PIR, the user retrieves a single message stored at the servers, while hiding the message index from each individual server. In our proposed privacy setting, the user is concerned with hiding the message index from a particular server, only if that server stores the message being retrieved, and privacy is not imposed otherwise. We coin this relaxed privacy requirement as local user privacy and the resulting PIR problem as local PIR on the graph. Our focus is on two-replicated PIR systems, where every message is replicated twice and stored on two distinct servers. Speciﬁcally, we study local PIR systems where the storage is represented by simple graphs, i.e., every pair of vertices is associated with at most one edge, and by their multigraph extension, i.e., r parallel edges replace every edge. For these settings, we establish bounds on the local PIR capacity, deﬁned as the maximum number of message symbols retrieved, per downloaded symbol. The local privacy requirement yields signiﬁcant capacity gain over the classical PIR capacity under the same storage structure. For instance, in settings where the graph is a disjoint union of multiple identical sub-graphs, the gain in the local PIR capacity over classical PIR capacity is multiplicative in the number of sub-graphs. Further, for connected graphs, we derive capacity lower bounds for edge-transitive and bipartite graphs, which are greater than the best-known PIR capacity bounds. From these and by establishing matching upper bounds, we exactly characterize the capacity for star graphs, cyclic graphs, and path graphs with odd number of vertices. We also introduce two local PIR schemes, one of which supports single-symbol messages, for general simple graphs. Finally, we extend these results to the case of multigraphs, and propose two achievable schemes for general r-multigraphs, along with explicit upperbounds for cyclic and path multigraphs. ∗

A part of this work was accepted in IEEE ITW 2026.

Introduction

Private information retrieval (PIR) studies the fundamental problem of eﬃciently retrieving a desired message Wθ from an indexed database, typically replicated across multiple, noncolluding servers, while ensuring that the identity of θ, i.e., the message index, is concealed from each individual server. This problem is motivated by crucial applications, such as those in medicine, ﬁnance, national defense, where revealing the user’s requested index reveals sensitive information such as the user’s interest or intent. The PIR system model consists of N servers storing K messages, whose contents the user is unaware of. For retrieving Wθ , the user communicates with the servers by generating and sending queries, to which the servers respond by constructing answers. From these answers, the user can correctly retrieve Wθ , while each server remains oblivious as to which of the K messages the user has retrieved. The PIR problem was introduced in the seminal paper [1], and was further studied in the computer science community (see e.g., [2–6]) with the focus on optimizing the communication and computation costs incurred, where each message is treated as a single bit. Thereafter, PIR garnered renewed interest in the information theory community, where the message lengths are assumed to be arbitrarily large, and the goal is to minimize the amount of information that the user downloads from the servers. Consequently, the capacity of PIR, deﬁned as the maximum attainable ratio between the message size and the amount of downloaded information, became the metric of interest. The PIR capacity was ﬁrst derived in [7] for the fully-replicated database setting, where each of the N non-colluding servers stores all K messages, after which another capacity-achieving scheme, which also guarantees minimal subpacketization, was proposed in [8]. This was extended to more realistic scenarios, such as server-dropouts [9–14], to address further security aspects, such as database security [15–17], server collusion [18–23], eavesdroppers [24–26], malicious servers [27,28], and recently to accommodate quantum communication channels between the servers and the user [29–32]. 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. Single-server PIR [33, 34] is one approach to solve this, but it requires availability of side information at the user, to accomplish a PIR scheme other than downloading all messages. To circumvent this requirement, the study of PIR with non-fully-replicated databases was initiated in [35–37], where the storage of messages at the servers is modeled by an undirected hyper-graph. Speciﬁcally, the servers are represented by vertices, and the messages are represented by hyper-edges. A copy of a message is stored at servers if and only if the hyper-edge representing the message is incident to the vertices representing the corresponding servers. To obtain more tangible results, this model was specialized to two-replicated systems, where each edge is incident to exactly two vertices, leading to exact and approximate PIR capacity results for common families of simple graphs [38–42] and r-multigraphs [40–43] where each edge is replaced by r parallel edges. Recently, in [44–46], these results were extended to 2

address database security, under graph-replicated and fully-replicated common randomness settings. In all the hypergraph-replicated PIR models, the PIR capacity decreases as the number of servers N (i.e., the number of vertices in a given hypergraph) increases, contrary to the fully-replicated case. Apart from partial replication of messages, this is also because, the privacy requirement has been kept the same as the one in the fully-replicated formulation in [7]. In other words, the usual model mandates the retrieval of all messages to be uniformly private against all servers, for all message indices, irrespective of whether the given message is stored at that server or not. This may be too restrictive towards the goal of preventing user-proﬁling, since the said server is unaware of the message contents. From a practical standpoint, if a server does not store a message, 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 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 becomes equivalent to the original PIR formulation. Related to our work is the PIR-variant that relaxes perfect privacy to an acceptable privacy budget. In this vein, leaky PIR [47] and weakly private PIR [48–51] have been studied. The goal there is to maximize the PIR rate, under a diﬀerential privacy, maximal leakage or mutual information leakage budget. In contrast, our proposed privacy relaxation arises naturally from the storage architecture of non-fully-replicated systems, while maintaining perfect privacy for the subset of indices that are stored in each server. In other words, in a given instance of local PIR, we expect perfect privacy for a desired message index against the servers that store that message. From the remaining servers, we seek to directly download a minimum amount of side information, so that the PIR rate is maximized. In this work, we ﬁrst focus on deriving local PIR capacity bounds for graphs whose edges are incident to only two vertices, and compare them with the standard graph-based PIR results in the literature. Our contributions for simple graphs are as follows. Our ﬁrst prominent result is the local PIR capacity of graphs that are (vertex-)disjoint union of m connected subgraphs. If the subgraphs are identical, the local PIR capacity improves upon that of standard PIR by at least a factor of m. Next, we focus on connected graphs, i.e., those graphs which have a path between every vertex pair. For edge-transitive graphs, we derive capacity lower bounds for PIR systems based on these graph families, such as cyclic, complete, and star graphs. Using this result, and a matching converse, we show that the local PIR capacity for the cyclic graph with N vertices is 21 , i.e., independent of the number of servers, while its PIR capacity is N 2+1 [36]. Starting from the scheme of complete graphs, we derive a local PIR scheme construction that yields a general capacity lower bound for any simple, connected graph. We follow this up with another scheme for general graphs,

which is not necessarily better than the previous scheme in terms of rate, but oﬀers more ﬂexibility by requiring minimal subpacketization. Under the local privacy requirement, we derive a simple yet eﬀective scheme for the class of bipartite graphs. This scheme achieves the local PIR capacity of 1 for star graphs, which is superior to the PIR capacity by a factor √ of N for large N. Using the scheme, and a matching converse, the local PIR capacity N −1 for odd N, while its PIR capacity is N2 [40]. Finally, for path graphs is derived as 2N −4 we generalize our results to r-multigraphs, that extend the two proposed schemes on simple graphs. Interestingly, both schemes achieve their respective simple graph local PIR rates multiplied by (2 − 21−r )−1 . However, one of them incurs expansion of subpacketization by a factor of 2r−1 , while the other maintains the subpacketization of 1. The rest of the paper is organized as follows. In Section 2, we present the new problem formulation for the local PIR problem for simple graphs, along with examples and graphtheoretic deﬁnitions. In Section 3, we state the main results for simple graphs and their consequences. In Section 4, we develop the schemes that yield the capacity lower bounds, while in Section 5, the corresponding upper bounds are derived. In Section 6, we extend the results to the multigraph version of simple graphs. Finally, Section 7 concludes the paper. Notations: To denote the set of integers {1, 2, . . . , n} for a positive integer n, we use the notation [n]. For positive integers m, n with m ≤ n, the notation [m : n] represents the set {m, m + 1, . . . , n − 1, n}. We assume every vector x to be a column vector, where x⊤ is its transposed row vector. For a matrix X, the vectors X(i, :) and X(:, j) denote its ith row and jth column, respectively. For a set or family of sets X , we use | · | to denote its cardinality.

System Model and Preliminaries

In this section, we start by describing the PIR system model for simple graphs in an information-theoretic framework, followed by motivating examples to introduce the concept of local privacy. Then, we provide important graph-theoretic deﬁnitions that are required in the main results section.

2.1

Problem Setting: Simple Graphs

In the traditional fully-replicated PIR setting, each message Wk , k ∈ [K], is replicated in all servers, i.e., if Wn is the storage at the nth server, then Wn = {W1 , W2 , . . . , WK }, n ∈ [N]. On the other hand, in graph-based/graph-replicated PIR, each server stores only a subset of the messages, i.e., Wn ⊆ {W1 , W2 , . . . , WK } for server n. In both cases, it is assumed that each message is a vector of L independent symbols generated uniformly at random from the ﬁeld Fq , where q is a prime power, and that the messages are independent of each other.

The joint entropy of all messages in the PIR system is H(W1 , W2 , . . . , WK ) =

K X

H(Wi ) = KL,

in q-ary units.

(1)

i=1

Given a simple, undirected graph G = (V, E), where V denotes the set of nodes/vertices and E denotes the set of edges, the respective PIR database system consists of N = |V | servers and K = |E| messages. Each message is replicated exactly twice and stored on two distinct servers in [N], such that an edge incident to a particular vertex means that the message represented by the edge is stored at the respective server. Speciﬁcally, let the message Wk be stored at servers i and j. Then, the edge {i, j} ∈ E incident with servers i and j, is assigned a unique index k ∈ [K]. Let us denote the set of message indices in the nth server as In = {ℓ ∈ [K] : Wℓ ∈ Wn } ⊆ [K].

(2)

Then, each server stores exactly deg(n) messages, where deg(n) = |In | is the degree of node n in G. [θ] Let θ ∈ [K] be the message index required by the user and Qn be the query sent by the user to the nth server to retrieve Wθ . Let Q denote all the queries sent by the user to all [θ] [θ] servers across all message indices, i.e., Q = {Qn : n ∈ [N], θ ∈ [K]}. Then, Qn , being a part of Q can be determined exactly given Q. Since the user has no prior knowledge about the message content, the queries are independent from them, i.e., I(Q; W1 , . . . , WK ) = 0.

(3)

In the typical graph-based PIR studied so far in the literature, where the required message index has to be private from all the servers, i.e., I(θ; Q[θ] n ) = 0,

n ∈ [N].

(4)

However, in local PIR, we focus on the local privacy requirement only, making the privacy notion less restrictive. More speciﬁcally, we only keep the index private from the servers storing the required message, i.e., I(θ; Q[θ] n | θ ∈ In ) = 0,

n ∈ [N].

(5)

This relaxation of privacy is the main diﬀerence between classical graph-based PIR and local PIR introduced here. As in typical PIR, we assume that the servers are honest but curious, [θ] [θ] i.e., if the nth server receives a query Qn , it generates an answer An , as a deterministic

function of the received query and the stored message symbols, which implies, [θ] H(A[θ] n |Wn , Qn ) = 0.

(6)

Once the user receives the answers from all the servers,1 the required message must be exactly decodable without errors, i.e., [θ]

H(Wθ |A[N ] , Q) = 0.

(7)

A local PIR scheme Π on a graph G is identiﬁed by the set of queries Q, and the corresponding [θ] set of answers A = {An , n ∈ [N], θ ∈ [K]} which satisfy (3), (5), (6) and (7). As in the PIR literature, L is referred to as the subpacketization of the scheme Π. Let the number of downloaded symbols to retrieve the kth message Wk be denoted as Dk , i.e., Dk =

N X

H(An[k] ).

(8)

n=1

Let P = (P (θ = k) , k ∈ [K]) be the probability mass function of the desired message index. Then, the rate of the scheme Π for a graph G is deﬁned as RPΠ (G) =

L L . = PK E[D] k=1 P(θ = k)Dk

(9)

Throughout the paper, we assume that θ is uniform over [K], simplifying the local PIR rate expression to KL RΠ (G) = PK . k=1 Dk

(10)

The capacity of the local PIR for graph G is given by the supremum of rates (10) over all achievable local PIR schemes Π, i.e., C(G) = sup RΠ (G).

(11)

In the following, we write C(G) as the local PIR capacity for the graph G, and CP IR (G) as the PIR capacity for the same graph. Remark 1 Due to the relaxed privacy constraint in (5) with respect to (4), the inequality C(G) ≥ CP IR(G), where CP IR holds for any graph G. 1

We assume without loss of generality that when a query is not sent to a server, the set of answers from this server is ∅.

W1 W

W5 W6

W 2

(a) C4

(b) K4

W3 5

Figure 1: Cyclic, complete and complete bipartite graphs. The vertices represent servers, and the edges represent the messages replicated at these servers.

2.2

Motivating Examples

We provide the following examples to present the main ideas of the proposed local PIR formulation, while considering storage settings based on common simple graph families. Example 1 (Cyclic Graph) Consider a cyclic graph CN for N = 4 servers (see Fig. 1a) with the storage in Table 1, i.e., W1 = {W1 , W4 }, W2 = {W1 , W2 }, W3 = {W2 , W3 }, W4 = {W3 , W4 }. server 1 server 2 server 3 server 4 W4 W1 W2 W3 W1 W2 W3 W4 Table 1: Storage for each server for C4 in Example 1. Let the number of symbols per message (subpacketization) be L = 2. Thus, each message can be represented as W1 = (a1 , a2 ), W2 = (b1 , b2 ), W3 = (c1 , c2 ) and W4 = (d1 , d2 ) after the user permutes the message symbols independently and uniformly at random. Table 2 illustrates the scheme for local PIR for each required message index. We make a couple of important observations, focusing on a single server, say server 1: First, we note that for messages stored in server 1, i.e., θ = 1 and θ = 4, the queries are identical, providing privacy. Second, we note that even when the desired message is not stored in this server, i.e., θ = 2 and θ = 3, the user still queries the server to download side information to be used together with downloaded information from other databases. θ=1 θ=2 θ=3 θ=4

server 1 a1 + d1 a1 d1 a1 + d1

server 2 a2 + b1 a1 + b1 b1 a1

server 3 b1 b2 + c1 b1 + c1 c1

server 4 d1 c1 c2 + d 1 c1 + d 2

Table 2: Retrieval scheme for C4 in Example 1.

The scheme downloads one symbol from each database, thus its rate is 24 = 12 . In contrast, the PIR capacity for the same setting [36] is given by CP IR (C4 ) = 25 < 12 = C(C4 ). Example 2 (Star Graph) In the star graph SN , we have a central node (say server N) storing all the messages and each of the remaining servers stores only one of those messages. That is, K = N − 1, and server n ∈ [N − 1] stores the message Wn . The local PIR scheme for SN is given as follows. If θ = k, the user contacts only the kth server, and downloads the entire message Wk . Since server N is never contacted to download a message, it stays oblivious of the desired message index θ. This yields the rate as 1, whereas, the PIR capacity for star graphs is CP IR (SN ) = Θ √1N [38].

Example 3 (Complete Graph) For the complete graph with N vertices KN , each node shares an edge with all other vertices, i.e., the degree of each node is N − 1 and the total number of edges is K = N2 . We consider the case of N = 4 servers, as depicted in Fig. 1b, with the storage given in Table 3. server 1 W1 W2 W3

server 2 W1 W4 W5

server 3 W2 W4 W6

server 4 W3 W5 W6

Table 3: Storage for K4 in Example 3. Let the number of symbols per message be L = 4. Thus, the permuted message symbols can be represented as W1 = (a1 , . . . , a4 ), W2 = (b1 , . . . , b4 ), W3 = (c1 , . . . , c4 ), W4 = (d1 , . . . , d4 ), W5 = (e1 , . . . , e4 ) and W6 = (f1 , . . . , f4 ). Table 4 illustrates the scheme for local PIR for each required message index. To retrieve 4 = 0.4. As 4 desired message symbols, we download 10 symbols in total, yielding the rate 10 shown in [42], the PIR capacity of K4 is bounded as 0.35 ≤ CP IR (K4 ) ≤ 0.3529. Thus, the rate of the local PIR scheme for K4 is higher than the upper bound on the PIR capacity. These examples demonstrate the potential rate improvements in local PIR, compared to standard PIR, due to the relaxed notion of local privacy. Next, we recall some useful deﬁnitions for graphs that will be used in our analysis.

2.3

Deﬁnitions

Deﬁnition 1 (Disjoint union of graphs) Graph G = (V, E) is a disjoint union of m graphs Gi = (Vi , Ei ), i ∈ [m], denoted by G = ∪i∈[m] Gi , if Vi ∩ Vj = ∅, i, j ∈ [m], i 6= j, m m [ [ V = Vi , E = Ei . i=1

i=1

(12) (13)

θ=4

server 1 a1 + b1 a2 + c1 b2 + c2 a1 + b1 a2 + c1 b2 + c2 a1 + b1 a2 + c1 b2 + c2 a1 b1

θ=5

a2 c1

θ=6

b2 c2

θ=1

θ=2

θ=3

server 2 a3 + d1 a4 + e1 d2 + e2 a1 e1 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

c2 f1

b1 + d3 b2 + f1 d4 + f2 d2 f2 b1 + d1 b2 + f1 d2 + f2

c3 + e1 c4 + f1 e2 + f2 e2 f2 c1 + e3 c2 + f1 e4 + f2 c1 + e1 c2 + f3 e2 + f4

Table 4: Retrieval scheme for K4 in Example 3. This deﬁnition is required to connect the local PIR rate of G to that of each individual subgraphs Gi , i ∈ [m] (see Theorem 1). Deﬁnition 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 . These two sets V1 and V2 are called parts. Examples of bipartite graphs are cyclic graphs with an even number of nodes, 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, in Deﬁnition 2 each of the parts V1 and V2 is a vertex cover of G. Individually, V1 and V2 are also independent sets of G, i.e., the nodes in V1 (or V2 ) share no common edge among each other. This special property of bipartite graphs helps us design an eﬃcient local PIR scheme for such graphs (see Theorem 4). Deﬁnition 3 (Edge-transitive graphs) Graph G = (V, E) is edge-transitive, if for every pair of edges e1 , e2 ∈ E there exists an automorphism2 that maps e1 to e2 . Examples of edge-transitive graphs are cyclic graphs, star graphs, complete graphs and complete bipartite graphs. The symmetry of such a graph G allows us to exactly deﬁne a 2

An automorphism of graph G is a permutation σ of the vertices in V , which preserves the graph structure in terms of vertex connectivity. That is, for any u, v ∈ V , σ(u) and σ(v) share an edge if and only if u and v share an edge.

local PIR scheme for G by a scheme on a single edge (see Theorem 2).

Main Results for Simple Graphs

In this section, we summarize the results for simple graphs, i.e., graphs where each message is replicated exactly twice, and no more than one edge exists between any two distinct nodes. Subsequently, we use the term graph instead of simple graph. The ﬁrst result connects the local PIR capacity of graphs to the local PIR capacity of their disjoint union. Without loss of generality, we assume the individual graphs to be connected, i.e., there exists a path between every pair of vertices. S Theorem 1 Let G = m 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 respective |Ei | messages. Then, the local PIR capacity of G is given by, Pm |Ei | · Li C(G) = Pm i=1 . i=1 |Ei | · E[Di ]

(14)

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 (14). Suppose, for the ′ 1 |L1 +|E2 |L2 . sake of contradiction, that there exists a scheme Π′ that achieves RΠ (G) > |E1|E |E[D1 ]+|E2 |E[D2 ] L1 Π′ Then, if V2 = ∅, we have G = G1 , and that C(G) ≥ R (G) > E[D1 ] . This leads to a L1 contradiction, since C(G) = C(G1 ) is at most E[D , hence, no such Π′ exists. 1] Corollary 1 If the m graphs G1 , . . . , Gm are identical, then C(G) = C(G1 ), i.e., there is no reduction in capacity. This provides multiplicative gain compared to the PIR capacity in the same setting, since C(G) ≥ CP IR (G) = m1 CP IR(G1 ). The subsequent results are for connected graphs. 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 = (Vk , Ek ) ⊆ (V, E) = G with Vk = {m ∈ [N] : Im ∩ (Ii ∪ Ij ) 6= ∅} ⊆ V,

Ek = {ℓ ∈ [K] : ℓ ∈ Ii ∪ Ij } ⊆ E,

(15) (16)

i.e., Vk is the set of servers that share at least one message with server i or server j, including servers i and j and Ek is the set of messages that are stored at server i or server j. If G is edge-transitive, Gk is identical for all k ∈ [K]. Examples are cyclic, star, complete, complete bipartite and Petersen graphs. 10

Theorem 2 For an edge-transitive graph G, ﬁx the edge {i, j} and the corresponding subgraph Gk . Then, the local PIR capacity is lower bounded as C(G) ≥

max

ti ∈[deg(i)],tj ∈[deg(j)]

λ(ti , tj )

deg(i) + ti − 1 ti

+ (1 − λ(ti , tj ))

deg(j) + tj − 1 tj

, (17)

where λ(ti , tj ) =

deg(i)−1 t −1 i deg(j)−1. deg(i)−1 + tj −1 ti −1

(18)

Remark 2 If deg(i) = deg(j) = d for all Gk , then (17) can be simpliﬁed to 1

C(G) ≥ max

t∈[d] d + t − 1 t

= max



(19)

 

1 1 √ √ ,  √d + ⌊ d⌋ − 1 √d + ⌈ d⌉ − 1  ⌊ d⌋ ⌈ d⌉

1 ≥ √ . 2 d

(20) (21)

The proofs of Theorem 2 and Remark 2 appear in Section 4.1 and Section 4.2, respectively. Corollary 2 From Theorem 2, we obtain the following rates for common graph families. 1. For the cyclic graph G = CN , with N ≥ 4 the subgraph Gk = P4 with deg(i) = deg(j) = 2, this yields 1 C(CN ) ≥ , 2

(22)

which is equal to CP IR (CN ) = N 2+1 if N = 3, and strictly greater for all N ≥ 4. Interestingly, the rate 12 for all N also coincides with the standard PIR capacity of the subgraph P4 (where CP IR (PN ) = N2 ). 2. For the complete graph G = KN , deg(i) = deg(j) = N − 1, this yields C(KN ) ≥ while

4 − o(1) 3

  √ 1

2 N −1−1  √1 , 2 N −1

N − 1 perfect square, otherwise,

(23)

1 ≤ CP IR (KN ) ≤ N (e−2) , as recently established in [42].

3. For the complete, balanced bipartite graph G = K N , N for even N, deg(i) = deg(j) = N2 , 2

this yields  √ 1

2N −1 C(K N , N ) ≥ 2 2  √1 , 2N

N 2

perfect square,

otherwise,

(24)

1 4 ≤ CP IR (K N , N ) ≤ N (e0.5 , by the tightest lower and upper bounds, established while 3N −1) 2 2 in [41] and [42], respectively.

Next, we establish the local PIR rate for a general graph G, which is derived from the scheme of Theorem 2 for KN . This relies on the fact that G is a sub-graph of KN for any connected graph G with N vertices. Theorem 3 Consider the row vector δ = [δ1 , . . . , δN ], where δn = (N −1)−deg(n), n ∈ [N]. −2 Then, for any graph G = (V, E) with |V | = N, |E| = K, and L = 2 Nt−1 , the local PIR capacity is lower-bounded as C(G) ≥ max

t∈[N −1]

1 1 − RΠt (KN )

k=1 ∆k

(25)

where, for every {k} = Ii ∩ Ij , with i, j ∈ [N], N −3 δj δi , + (δi + δj ) + ∆k = t−2 t t

(26)

and Πt is the scheme for edge-transitive graphs in Theorem 2 for a given t. Corollary 3 From Theorem 3, we obtain the following lower bounds. 1. For CN and KN , we recover the same rates as in Corollary 2.1 and 2.2, respectively. 2. For the path graph G = PN , δ = [N − 2, N − 3, . . . , N − 3, N − 2], and we have the | {z } N −2 times

capacity lower bound

C(PN ) ≥ max

2 t∈[N −1] N −1 + t − 1 − (N −t−1) /t+(N −2)(t−1) t N −1

N −1 . 2N − 3

(27) (28)

3. For the wheel graph G = WN , where server 1 is the central node, δ = [0, N −4, . . . , N − 4]. Consequently, we obtain C(WN ) = Ω √1N for asymptotically large N. This bound is larger than the upper bound for wheel graphs in the PIR setting, where the upper bound is N1 [38].

Remark 3 For the complete graph KN and the complete, balanced bipartite graphs K N , N , 2 2 1 √ the local PIR capacity is Ω N , whereas the standard PIR capacity for these graphs is √ Θ N1 as N → ∞. That is, the PIR capacity vanishes to 0 approximately N times faster.

Remark 4 For the star graph G = SN , the Gk = G; the lower bounds on C(SN ) subgraph 1 yielded by Theorem 2 and Theorem 3 are Ω √N (see Table 5), which coincide with the PIR capacity for asymptotically large N [38, 39]. However, leveraging the fact that SN = KN −1,1 , the next theorem for the class of bipartite graphs improves this, and identiﬁes the local PIR capacity for SN . Theorem 4 If G = (V, E) is bipartite, with parts V1 , V2 , the local PIR capacity is lower bounded as !−1 X deg(n)2 C(G) ≥ K · min . (29) m∈{1,2}

n∈Vm

The proof allows for minimal subpacketization, i.e., L = 1 and follows from the scheme in Section 4.4. Corollary 4 From Theorem 4, the following rates for common graph families are achievable. 1. For the star graph G = SN , this yields C(SN ) = 1,

(30)

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 , we obtain C(PN ) ≥

  N −1 , 2N −3

 N −1 , 2N −4

N even, N odd,

(31)

by choosing V1 as odd and V2 as even vertex indices in [N]. The lower bound here for even N matches the lower bound in Corollary 3.2, while it is improved for odd N. 3. For the cyclic graph CN with even N, the rate is 21 , equal to (22). o n 4. For complete bipartite graphs KN1 ,N2 , we have C(KN1 ,N2 ) ≥ max N11 , N12 , which for the balanced case of K N , N with even N reduces to 2

C(K N , N ) ≥ 2

2 . N

(32)

Graph type

Thm. 2 Thm. 3

Path PN

N −1 2N −3

Cyclic CN

1 2 √1 2 N −1 √1 2 N −1

Complete, balanced bipartite K N , N

√1 2N

1 2 √1 2 N −1 √ 1 N −1

Wheel WN

Complete KN Star SN 2

(

Thm. 4 N −1 , N even 2N −3 N −1 , N odd 2N −4 1 , N even 2

√1

Ω

2 N

√1 N

Thm. 5

CP IR

N −1 2N −3

2 N

1 2 1 N −1 2 N

2 N +1 Θ N1 Θ √1N Θ N1 Θ N1

2 N 4 N −8

Table 5: Achievable local PIR rates and exact/approximate PIR capacities for common graph families. A hyphen (-) indicates that the result does not apply to the graph. This is strictly better than the bound (24) for N ≤ 6, and is lower otherwise.

The following theorem establishes another capacity lower bound for any connected graph G. Similar to that of Theorem 4, the achievable scheme requires minimal subpacketization, i.e., L = 1, and is presented in Section 4.5. Theorem 5 For any graph G = (V, E) the capacity of local PIR is lower-bounded as C(G) ≥ 2K ·

deg(n)2

n∈V

!−1

(33)

Remark 5 It can be veriﬁed that, if G is bipartite, the rate provided by Theorem 4 is greater than or equal to the rate from Theorem 5, for the same subpacketization L = 1. Table 5 provides a summary of local PIR rates for common graph families, alongside the corresponding PIR capacities. In all cases, the greatest achievable rates for local PIR are superior to the respective PIR capacities. Theorem 6 For the cyclic graph CN , the local PIR capacity is given by 1 C(CN ) = . 2

(34)

Theorem 7 For the path graph PN , the local PIR capacity satisﬁes C(PN ) ≤

N −1 . 2N − 4

(35)

N −1 for odd N. This matches the rate (31) for odd N, which gives C(PN ) = 2N −4

Remark 6 Interestingly, the local PIR capacities of path, cyclic and star graphs are strictly bounded above 0 as N → ∞. This highlights an important gain in the communication 14

eﬃciency compared to the standard PIR model for the aforementioned graphs, where the capacity is known to vanish to 0 as N → ∞. Remark 7 For any graph G with deg(n) ≥ 2 for all vertices n ∈ [N], the capacity upperbound C(G) ≤ 21 holds in general. The proof follows from a simple observation and is shown in Section 5.3. As a corollary, local PIR capacity on KN , KN1 ,N2 (N1 + N2 = N) and WN satisfy this, besides CN .

Proofs of Capacity Lower Bounds

In this section, we present the achievable schemes that yield the rates in Theorems 2-5. Each scheme description is followed by a running example on the complete bipartite graph K2,3 (see Fig. 1c), where N = 5 and K = 6. Without loss of generality, we compute the rates only for θ = 1, which applies to all indices by the edge-transitivity of K2,3 .

4.1

Proof of Theorem 2

We present the scheme for a ﬁxed 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 queries only for the messages corresponding to Ek , i.e., Wi ∪ Wj . We ﬁx ti , tj ∈ N, with ti ∈ [deg(i)] and tj ∈ [deg(j)]. The scheme requires each message to consist of L=

deg(j) − 1 deg(i) − 1 + tj − 1 ti − 1

(36)

symbols. The user applies a private, 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 -sums3 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 lexicographic order. Let Ai = Ai1 , . . . , Ai deg(i) and Aj = Aj1 , . . . , Aj deg(j) . Then, for each ( ti ) ( tj ) i i i ℓ ∈ Ii and each Ap ∈ Ai , such that ℓ ∈ Ap , we deﬁne γℓ (Ap ) as γℓ (Aip ) =

p X x=1

1{ℓ ∈ Aix },

The term l-sum for l ≥ 1 refers to the sum of symbols of l distinct messages.

(37)

i.e., the number of times that ℓ is contained in a subset, up to and including Aip . The same deﬁnition of γℓ (Ajp ) extends to Aj . For each A ∈ Ai , the user downloads from server i, X

Wℓ (γℓ (A)).

(38)

ℓ∈A

From server j, for each A ∈ Aj , the user downloads  Wk deg(i)−1 + γk (A) + P ℓ∈A\{k} Wℓ (γℓ (A)), k ∈ A, ti −1 P  k∈ / A. ℓ∈A Wℓ (γℓ (A)),

(39)

deg(j)−1 For each ℓ ∈ Ii , and each ℓ ∈ Ij , γℓ (A) varies from 1 to deg(i)−1 , and from 1 to , ti −1 tj −1 respectively. From the servers, Vk \ {i, j}, the user downloads the interference message symbols, that appear in the summations (38) and the ﬁrst case of (39). Speciﬁcally, for each ℓ ∈ Ii \ {k}, deﬁne Bℓ,i = {B ∈ Ai : {ℓ, k} ⊆ B},

(40)

and for each ℓ ∈ Ij \ {k}, deﬁne Bℓ,j = {B ∈ Aj : {ℓ, k} ⊆ B}.

(41)

The sets Bℓ,i and Bℓ,j consist of the indices of Wℓ appearing in (38) and (39), respectively. Then, corresponding to ℓ ∈ Ii \ {k} (or Ij \ {k}), the user downloads the symbols, {Wℓ (γℓ (B)) : B ∈ Bℓ,i (or Bℓ,j )}

(42)

from the server storing Wℓ . Since the graph is simple, a single server in Vk \ {i, j} stores Wℓ . The number of downloaded symbols to retrieve the L symbols of Wk is Dk = |Ai | + |Aj | +

ℓ∈Ii \{k}

|Bℓ,i | +

ℓ∈Ij \{k}

|Bℓ,j |

(43)

deg(j) − 2 deg(i) − 2 deg(j) deg(i) (44) + (deg(j) − 1) + (deg(i) − 1) + = tj − 2 ti − 2 tj ti deg(j) deg(i) deg(j) − 1 deg(i) − 1 + ti − 1 + + tj − 1 . (45) = ti tj tj − 1 ti − 1 The ratio of (36) and (45) gives the desired rate. The rate is maximized over all choices of ti ∈ [deg(i)] and tj ∈ [deg(j)] to obtain the largest lower bound. For θ = k, privacy holds at the servers i and j, as required. This is because, once the scheme parameters ti and tj are ﬁxed, the same query structure is maintained for all messages stored at server i (and server j) for all θ in Ii (and Ij ) due to edge-transitivity of 16

server 1 W1 W2 W3

server 2 W4 W5 W6

server 3 W1 W4

server 4 W2 W5

server 5 W3 W6

Table 6: Storage for K2,3 ; see the graph in Fig. 1c. server 1 a1 + b1 a2 + c1 b2 + c2

server 2 ∅

server 3 a3 , d1

server 4 b1

server 5 c1

Table 7: Retrieval scheme for K2,3 for Example 4. the graph. Moreover, the servers remain oblivious of the actual queried message symbols, since the symbol indices are permuted privately and independently by the user. Examples 1 and 3 in Section 2.2 follow this scheme. The next example is on K2,3 with storage given in Table 6; see the graph in Fig. 1c. Example 4 The optimal choices of the optimization variables in (17) are ti = 2 and tj = 1. Let θ = 1, then i = 1, and j = 3 with V1 = V = [5], E1 = {1, 2, 3, 4} and L = 3. The sets An and Bℓ,n for n = 1, 3 and ℓ ∈ {2, 3, 4} are A1 = ({1, 2}, {1, 3}, {2, 3}) , B2,1 = {{1, 2}},

A3 = ({1}, {4}) ,

B3,1 = {{1, 3}},

B4,2 = ∅.

(46) (47)

From here, we deduce the corresponding answers as given in Table 7, and the rate is 73 .

4.2

Proof of Remark 2

In the rate expression, we minimize the term λ(ti , tj )

d d + ti − 1 + (1 − λ(ti , tj )) + tj − 1 , ti tj

(48)

where λ(ti , tj ) =

d−1 ti −1

∈ (0, 1). + td−1 j −1

(49)

Assume without loss of generality, that tdi + ti − 1 ≤ tdj + tj − 1. Now, for any λ(ti , tj ) ∈ (0, 1), λ(ti , tj )

d d d d + ti − 1 + (1 − λ(ti , tj )) + tj − 1 ≥ min + ti − 1, + tj − 1 (50) ti tj ti tj 17

d + ti − 1, ti

(51)

The minimum value of (51) is achieved upon setting ti = tj = t in (48). This simpliﬁes the problem to d + t − 1, t∈[N −1] t min

(52)

√ √ which is solved by t = ⌊ d⌋ or t = ⌈ d⌉, or both if both values yield the same dt + t − 1. √ √ Finally, the last inequality (21) follows since ⌊√dd⌋ − 1, ⌊ d⌋, ⌈√dd⌉ and ⌈ d⌉ − 1 are all √ upper-bounded by d.

4.3

Proof of Theorem 3

−2 First, we ﬁx t ∈ [N − 1] and L = 2 Nt−1 . Let the user privately permute the symbols of all messages in W = {W1 , . . . , WK }, by picking a permutation uniformly at random, from the set of all permutations of L permutations, and independently for each Wk ∈ W. Consider the helper complete graph KN with the message set W KN ⊃ W where WK+1 , . . . , W(N ) are 2 the virtual messages, i.e., messages that are missing in the storage corresponding to G. Let InKN denote the set of message indices stored in server n ∈ [N] of the helper KN . With this setup, we describe the local PIR scheme for θ = k where Ii ∩ Ij = {k}. By recalling the deﬁnitions of Vk in (15) and Ek in (16), the user interacts only with the servers corresponding to Vk , and the answers consist of only the messages corresponding to Ek , i.e., Wi ∪ Wj . Following the scheme for edge-transitive graphs in Section 4.1, we construct the ordered N N using the index sets IiKN and IjKN , respectively. From here, the user sets AK and AK j i N , we remove the constructs the ordered multisets Ai and Aj as follows. For each A ∈ AK i KN KN elements in Ii \ Ii , and for each A ∈ Aj , we remove the elements in IjKN \ Ij . Then, for a ﬁxed t, Ai and Aj consist of the resultant non-empty subsets of Ii and Ij , respectively, of size at most t. From server i, the user queries for sums involving the ﬁrst (permuted) L/2 symbols of Wk . Similarly, from server j, the user queries for sums involving the last (permuted) L/2 symbols of Wk . More speciﬁcally, for each A ∈ Ai the user queries for the sum given by (38). Similarly, for each A ∈ Aj , the user queries for the sum given by (39) −2 −2 where deg(i)−1 = Nt−1 . Note that, for each ℓ, γℓ (A) varies from 1 to Nt−1 for A ∈ Ai or ti −1 A ∈ Aj . To account for the interfering message symbols, we construct the multisets Bℓ,i and Bℓ,j , following (40)-(41). The user downloads the interfering message symbols given by (42) from the remaining servers Vk \ {i, j}. Let D KN be the local PIR download cost for the KN storage, which is independent of θ = k, by edge-transitivity of KN . The download cost is given by |Ai | + |Aj | +

ℓ∈Ii \{k}

|Bℓ,i | +

ℓ∈Ij \{k}

|Bℓ,j | 18

X N − 3 X N − 3 δj δi KN (53) + + + |Aj | − = t−2 t−2 t t ℓ∈Ij \{k} ℓ∈Ii \{k}   X X N −3  N −3  KN N + = |AK | + |A | +  i j t−2 t−2 K K

N |AK |− i

ℓ∈Ij N \{k}

ℓ∈Ii N \{k}

N −3 N −3 δj δi + δj + δi + − t−2 t−2 t t

= D KN − ∆k .

(54)

(55)

The resulting rate is R(G) = PK

KN − ∆ ) k k=1 (D 1 = K , PK N D k=1 ∆k − L KL

(56) (57)

L which gives the desired rate since RΠt (KN ) = DK . The maximization over all t ∈ [N − 1] N yields the greatest lower bound for C(G). Privacy against server n holds because, for a ﬁxed t, the queries received by the server follow the same structure, for every θ ∈ In . That is, the query structure is such that the user requests for equal number of symbols of all messages in Wn , where the symbol indices are hidden because of the user-private independent permutations. This is because, upon the N to An , every ℓ ∈ In appears equal number of times across all subsets in conversion from AK n δn An . The multiset An consists of N −1 − t subsets (with repetitions), where each subset is t δn N subsets of AK of size ρ ∈ [t]. For a ﬁxed t, any ρ-subset of In is contained in exactly t−ρ n . Moreover, there are deg(n)−1 unique ρ-subsets which contain ℓ. Therefore, the number of ρ−1 deg(n)−1 δn , which is independent of ρ-subsets in An , that ℓ ∈ In appears in is precisely t−ρ ρ−1 ℓ.

Example 5 We illustrate the scheme on K2,3 , where the optimal choice of t is 2, and L = 3. With θ = 1, starting from K5 , we construct the multisets An and Bℓ,n for n = 1, 3 and ℓ ∈ {2, 3, 4}, given by A1 = ({1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}) , B2,1 = {{1, 2}},

B3,1 = {{1, 3}},

A3 = ({1}, {1}, {4}, {4}, {1, 4}) ,

B4,2 = {{1, 4}}.

(58) (59)

6 = 37 . From here, we deduce the corresponding answers as shown in Table 8, and the rate is 14

server 1 a1 , b1 , c1 a2 + b2 a3 + c2 b3 + c3

server 2 d3

server 3 a4 , d1 a5 , d2 a6 + d3

server 4 b2

server 5 c2

Table 8: Retrieval scheme for K2,3 for Example 5.

4.4

Proof of Theorem 4

Assume that L = 1. Given G bipartite, with parts V1 and V2 , let m∗ = arg min

m∈{1,2}

deg(n)2 .

(60)

n∈Vm

For θ = k, suppose Wk is stored on servers i and j. Assume without loss of generality that / Vm∗ . Then, the user queries for all messages from server i, downloading i ∈ Vm∗ and j ∈ deg(i) messages and nothing at all from server j.4 In short, the user downloads the message set Wn if θ ∈ In and n ∈ Vm∗ . The resulting total download across all θ is K X

Dk =

deg(n)L

n∈Vm∗

k=1

K X k=1

deg(n)2 L,

1{k ∈ In }

(61) (62)

n∈Vm∗

since the inner sum in (61) is deg(n). The ratio between KL and (62) gives the desired rate. Local privacy follows since whenever the user downloads Wn from server n ∈ Vm∗ , only the fact that θ ∈ In is revealed to it. Remark 8 Interestingly, this scheme provides standard privacy as PIR (not limited to local privacy) against any server n ∈ V \ Vm∗ . This is because, irrespective of the realization of θ, the user does not communicate with these servers. Continuing with the running example of K2,3 , we have V1 = {1, 2} and V2 = {3, 4, 5}. [1] Then, m∗ = 2, and the answers when θ = 1 are A3 = {W1 , W4 }, which results in the rate 12 .

4.5

Proof of Theorem 5

For this scheme, we assume L = 1 for all messages.5 The user privately generates K bits, hℓ , ℓ ∈ [K], uniformly at random and independently from {0, 1}. For server n, let Wn be 4 This resembles the scheme of single-server PIR, where to preserve privacy, one must download all the messages stored on it. 5 Without loss of generality, we assume each message is a single bit, since the same query can be applied to each bit individually across the entire message length for any L > 1.

deg(n)

arranged in an increasing order of the elements in In into the vector Wn ∈ F2 letting In = {ℓ1 , ℓ2 , . . . , ℓdeg(n) } where ℓ1 < ℓ2 < . . . < ℓdeg(n) , we write

, i.e.,

i⊤ h Wn = Wℓ1 Wℓ2 . . . Wℓdeg(n) .

(63)

i⊤ h hn = hℓ1 hℓ2 . . . hℓdeg(n)

(64)

Similarly, let

be the binary random vector constituting the bits {hℓ , ℓ ∈ In }, arranged in the same order. Let Wk be stored on server i and server j, where without loss of generality, i < j. To retrieve Wk , the user sends a binary query vector each, to server i and server j, while sending nothing to the remaining servers. Assuming that Wk appears in the pth row of Wi and in the mth row of Wj , i.e., Wi (p) = Wj (m) = Wk , where p ∈ [deg(i)], m ∈ [deg(j)], the queries sent are [k]

Qi = hi ,

[k]

Qj = hj + em ,

(65)

where hi (p) = hj (m) = hk , and “+” denotes bit-wise addition, and em is the deg(j) unit [k] column vector with 1 at row m. In response, the answer An returned by server n is a vector [k] whose νth entry An (ν) is given by the rule  [k] Q[k] n (ν) · Wn (ν), Qn (ν) = 1, [k] An (ν) = [k] ∅, Qn (ν) = 0,

(66)

where “·” denotes scalar multiplication in F2 . If the νth query entry of server n is non-zero, [k] [k] then An (ν) = Wn (ν). Otherwise, the corresponding entry in An is omitted. Thus, the [k] [k] length of answer vectors Ai and Aj , for a ﬁxed realization of query-pair, is given by the [k] [k] number of ones in the query vectors Qi and Qj , respectively. [k] [k] The download cost Dk is given by the sum of answer lengths Ai and Aj , averaged over all realizations of {hℓ , ℓ ∈ Ii ∪ Ij } ∈ {0, 1}deg(i)+deg(j)−1 . Note that, the desired message Wk is downloaded either from server i or from server j, which contributes 1 bit to the download [k] cost. Let Xi ∈ [0 : deg(i) − 1] and Xj ∈ [0 : deg(j) − 1] be the number of ones in Qi [k] and Qj , excluding the entries hk and hk + 1, respectively. Clearly, since hℓ is uniform on {0, 1}, and independent, Xi ∼ Binomial(deg(i) − 1, 0.5) and Xj ∼ Binomial(deg(j) − 1, 0.5). Therefore, taking expectation over hi and hj yields Dk = 1 + E [Xi ] + E [Xj ] =1+

deg(i) − 1 deg(j) − 1 + 2 2

(67) (68)

(h1 h2 h3 h4 ) (0000) (0010) (0100) (0110) (1000) (1010) (1100) (1110)

server 1 ∅ W3 W2 W2 , W3 W1 W1 , W3 W1 , W2 W1 , W2 , W3

server 3 W1 W1 W1 W1 ∅ ∅ ∅ ∅

(h1 h2 h3 h4 ) (0001) (0011) (0101) (0111) (1001) (1011) (1101) (1111)

server 1 ∅ W3 W2 W2 , W3 W1 W1 , W3 W1 , W2 W1 , W2 , W3

server 3 W1 , W4 W1 , W4 W1 , W4 W1 , W4 W4 W4 W4 W4

Table 9: Table showing all possible queries and the downloads for θ = 1 for K2,3 . =

deg(i) + deg(j) . 2

(69)

Summing across all k, we get K X

1 X (deg(i) + deg(j)) 2 {i,j}∈E   X 1 X = · deg(i)  1{{i, j} ∈ E} 2 i∈V

Dk =

k=1

(70)

(71)

j∈V \{i}

1 X (deg(i) · deg(i)) . = · 2 i∈V

(72)

Finally, rate is given by PKK D = P 2K 2. i∈V deg(i) k=1 k For each desired message index, {k} = Ii ∩ Ij , server n ∈ {i, j} receives a uniformly random binary vector of deg(n) length as a query. This is a probabilistic scheme from the equivalent viewpoint that server n is sent one of the feasible query sets, depending upon the realization of hn , which are identically distributed irrespective of θ ∈ In . Continuing with the running example of K2,3 , for θ = 1, there are 24 = 16 possible queries, depending on the realizations of h1 , h2 , h3 , h4 , as shown in Table 9. Each query is chosen with equal probability 2−4 , and the resulting rate is given by 25 .

Proofs of Capacity Upper Bounds

In this section, we derive the results on capacity upper bounds. Consider a storage based on a connected, simple graph G with N vertices, and K edges. For the desired index θ = k, the number of downloaded symbols from all servers is, Dk =

N X

H(A[k] n )

(73)

n=1

≥

N X n=1

H(A[k] n |Q)

(74)

[k]

(75)

≥ H(A[N ] |Q) [k]

[k]

= H(Wk |A[N ] , Q) + H(A[N ] |Q)

(76)

[k]

= H(Wk |Q) + H(A[N ] |Wk , Q) − H(A[N ] |W, Q)

(77)

= L + I(W \ {Wk }; A[N ] |Wk , Q),

(78)

[k]

where (76) follows from decodability (7), and the last term in (77) is zero due to (6). The second term in (78) is the information about the non-desired messages W \ Wk , i.e., interferP [k] ence contained in the answers A[N ] . Then, the lower bound on the total download K k=1 Dk is KL added to the K interference terms. To obtain suitable bounds on these quantities, we require the following lemmas that any local PIR scheme must satisfy. The ﬁrst lemma is a modiﬁcation of [38, Proposition 2], in the sense that, for each n, the support set of θ is precisely In , instead of [K] for each n. Lemma 1 For any J ⊂ [K], deﬁne the message set WJ = {Wℓ : ℓ ∈ J }. Then, by the local user privacy against server n, we have [θ] I(θ; A[θ] n |Qn , WJ ) = 0,

θ ∈ In , n ∈ [N].

(79)

Proof: This is equivalent to showing that for any k, k ′ ∈ In with k 6= k ′ ′

′

[k] [k ] [k ] H(A[k] n |Qn , WJ ) = H(An |Qn , WJ ).

(80)

Let Wn′ = Wn ∩ WJ . Note that, [k] [k] [k] ′ ′ [k] [k] ′ H(A[k] n |Qn , WJ ) = H(An |Qn , Wn ) − I(WJ \ Wn ; An |Qn , Wn )

′] ′ ′ [k] [k] ′ [k ′ ] = H(A[k n |Qn , Wn ) − I(WJ \ Wn ; An |Qn , Wn ),

(81) (82)

where (82) follows from local user privacy requirement (5) for any k, k ′ ∈ In . It remains to [k] [k] show that I(WJ \ Wn′ ; An |Qn , Wn′ ) = 0, which is true since, [k] ′ ′ [k] ′ [k] ′ I(WJ \ Wn′ ; A[k] n |Qn , Wn ) ≤ I(WJ \ Wn ; An , Wn \ Wn |Qn , Wn )

(83)

′ ′ [k] [k] = I(WJ \ Wn′ ; Wn \ Wn′ |Q[k] n , Wn ) + I(WJ \ Wn ; An |Qn , Wn ) (84)

[k] [k] ≤ I(WJ \ Wn′ ; Wn |Q[k] n ) + H(An |Qn , Wn )

= 0.

(85) (86)

The ﬁrst term in (85) is 0 by the independence of the disjoint message sets, and their 23

independence from the query, while the second term is 0 due to (6). The next lemma states that given any subset of messages, the answer from server n depends solely on the query sent to server n, and is independent of the rest of Q. Note that, the lemma applies to the standard PIR setting, irrespective of the servers’ storage. Lemma 2 For any subset J ⊂ [K], and any k ∈ [K] [k] [k] [k] H(A[k] n |WJ , Qn ) = H(An |WJ , Qn , Q)

(87)

= H(An[k] |WJ , Q).

[k]

(88)

[k]

Proof: For (87), we show that I(An ; Q|WJ , Qn ) = 0. Denoting Wn′ as Wn ∩ WJ , we have [k] ′ [k] I(An[k] ; Q|WJ , Q[k] n ) ≤I(An , Wn \ Wn ; Q|WJ , Qn )

(89)

[k] ′ [k] =I(Wn \ Wn′ ; Q|WJ , Q[k] n )+I(An ; Q|Wn , WJ \ Wn , Qn )

(90)

=I(Wn , WJ \ Wn′ ; Q|Q[k] n )

(92)

[k] ≤I(Wn \ Wn′ ; Q|WJ , Q[k] n ) + I(WJ ; Q|Qn )

(91)

≤I(Wn , WJ \ Wn′ ; Q, Q[k] n ) = 0,

(93) [k]

[k]

where (91) follows since the second term of (90) is zero since H(An |Wn , WJ \ Wn′ , Qn ) = 0, [k] and the last equality follows by (3). The equality (88) holds since H(Qn |Q) = 0. The next lemma is a re-statement of [38, Lemma 3], and applies to our local PIR setting as well, by the decodability requirement (7). Lemma 3 (Lemma 3 in [38]) For any two servers i, j with {i, j} ∈ E, and for any k ∈ Ii ∩ Ij , a local PIR scheme on the graph G, satisﬁes [k]

[k]

H(Ai |W \ {Wk }, Q) + H(Aj |W \ {Wk }, Q) ≥ L.

5.1

(94)

Proof of Theorem 6

Given CN , let the storage of server n be Wn = {Wn , Wn−1 }, with the convention that W0 = WN . Throughout the proof, we consider the message and server indices modulo N. For θ = k, the lower bound on the interference term is given by [k]

[k]

I(W \ {Wk }; A[N ] |Wk , Q) ≥ I(Wk−1 , Wk+1 ; A[N ] |Wk , Q)

(95)

[k]

(96)

[k]

(97)

[k−1]

|Wk , Q) + I(Wk+1 ; Ak+1 |Wk , Wk−1 , Q)

= I(Wk−1 ; A[N ] |Wk , Q) + I(Wk+1 ; A[N ] |Wk , Wk−1, Q) ≥ I(Wk−1 ; Ak |Wk , Q) + I(Wk+1 ; Ak+1 |Wk , Wk−1 , Q) = I(Wk−1 ; Ak [k−1]

= H(Ak

[k+1]

|Wk , Q) + H(Ak+1 |Wk , Wk−1 , Q) 24

(98) (99)

[k−1]

≥ H(Ak

[k+1]

|W \ {Wk−1 }, Q) + H(Ak+1 |W \ {Wk+1 }, Q), (100) [k−1]

where (98) follows by applying Lemma 1 and Lemma 2, (99) follows since H(Ak |Wk , Wk−1 , Q) = [k+1] 0 and H(Ak+1 |Wk+1, Wk , Wk−1, Q) = 0. Now, summing Dk − L over all k ∈ [N], we have N X k=1

Dk − NL ≥

N X

[k−1]

H(Ak

k=1

(101)

|W \ {WN −1 }, Q) + H(A1 |W \ {W1 }, Q)

(102)

[k+1]

|W \ {Wk−1}, Q) + H(Ak+1 |W \ {Wk+1 }, Q)

[N ]

[2]

= H(A1 |W \ {WN }, Q) + H(A2 |W \ {W2 }, Q) [1]

[3]

[2]

[4]

+ H(A2 |W \ {W1 }, Q) + H(A3 |W \ {W3 }, Q) + H(A3 |W \ {W2 }, Q) + H(A4 W \ {W4 }, Q) [N −1]

+ . . . + H(AN

N X k=1

[1]

[k]

H(Ak |W \ {Wk }, Q) + H(Ak+1|W \ {Wk }, Q)

= NL,

(103) (104)

where (103) follows by grouping the answer pairs with the same message index (superscript), and (104) holds by applying Lemma 3.

5.2

Proof of Theorem 7

Given PN , let the storage of server n be     {W1 }, Wn =

n = 1,

{Wn , Wn−1}, n ∈ [2 : N − 1],    {WN −1 }, n = N.

(105)

Our goal is to lower bound the second term in (78) by following arguments similar to those in Section 5.1. First, for k = 1, I(W \ {W1 }; A[N ] |W1 , Q) ≥ I(W2 ; A[N ] |W1 , Q)

[1]

(106)

≥ I(W2 ; A2 |W1 , Q)

[1]

(107)

[1] = H(A2 |W1 , Q) [2] = H(A2 |W1 , Q)

(108) (109)

[2]

(110)

[N −2]

(111)

≥ H(A2 |W \ {W2 }, Q).

Similarly, for k = N − 1, it follows by symmetry that [N −1]

I(W \ {WN −1 }; A[N ] |WN −1 , Q) ≥ H(AN −1 |W \ {WN −2 }, Q). 25

For k ∈ [2 : N − 2], we obtain [k]

[k]

I(W \ {Wk }; A[N ] |Wk , Q) ≥ I(Wk−1 , Wk+1 ; A[N ] |Wk , Q)

(112)

[k]

(113)

[k]

(114)

[k−1]

|Wk , Q) + I(Wk+1 ; Ak+1 |Wk , Wk−1 , Q)

= I(Wk−1 ; A[N ] |Wk , Q) + I(Wk+1 ; A[N ] |Wk , Wk−1, Q) ≥ I(Wk−1 ; Ak |Wk , Q) + I(Wk+1 ; Ak+1 |Wk , Wk−1 , Q) = I(Wk−1 ; Ak [k−1]

= H(Ak

[k−1]

≥ H(Ak

[k+1]

(115)

[k+1]

|Wk , Q) + H(Ak+1 |Wk , Wk−1 , Q)

(116)

[k+1]

|W \ {Wk−1 }, Q) + H(Ak+1 |W \ {Wk+1 }, Q). (117)

Now, summing Dk − L over all k ∈ [N − 1], we have N −1 X k=1

[2]

Dk − (N − 1)L ≥ H(A2 |W \ {W2 }, Q) +

N −2 X k=2

[k+1] [k−1] H(Ak |W \ {Wk−1 }, Q) + H(Ak+1 |W \ {Wk+1 }, Q)

[N −2]

+ H(AN −1 |W \ {WN −2 }, Q) [2]

(118)

[1]

[3]

= H(A2 |W \ {W2 }, Q) + H(A2 |W \ {W1 }, Q) + H(A3 |W \ {W3 }, Q) [2]

[4]

+ H(A3 |W \ {W2 }, Q) + H(A4 |W \ {W4 }, Q)+ [N −3]

[N −1]

. . . + H(AN −2 |W \ {WN −3 }, Q) + H(AN −1 |W \ {WN −1 }, Q) [N −2]

+ H(AN −1 |W \ {WN −2 }, Q) N −2 X [k] [k] H(Ak |W \ {Wk }, Q) + H(Ak+1|W \ {Wk }, Q ≥

(119) (120)

k=2

≥ (N − 3)L,

(121)

[1]

where (120) follows from (119) by dropping the entropy terms H(A2 |W \ {W1 }, Q) and [N −1] H(AN −1 |W \ {WN −1 }, Q), and (121) follows from Lemma 3.

5.3

Proof of Remark 7

We consider the PIR systems for which deg(n) = |In | ≥ 2 for all n ∈ [N]. Let each index set In = {ℓt , t ∈ deg(n)} be arranged into the vector, i h In = ℓ1 ℓ2 . . . ℓdeg(n) ,

(122)

such that ℓ1 < ℓ2 < . . . < ℓdeg(n) . Also, consider the cyclic order of the indices in server n given by ℓ1 → ℓ2 → . . . → ℓdeg(n) → ℓ1 . Now, let servers i and j share the message Wk , and let k = Ii (mi ) = Ij (mj ), where mi ∈ [deg(i)] and mj ∈ [deg(j)]. Further, let k1 = Ii (mi + 1) and k2 = Ij (mj + 1), where the indices are taken in a cyclic order. Clearly, since the degrees 26

of all vertices is at least 2, k1 and k2 are distinct from k, and k1 6= k2 since G is simple. Then, the following lower bound holds. [k]

Dk − L ≥I(W \ {Wk }; A[N ] |Wk , Q)

(123)

[k]

≥I(Wi ∪ Wj \ {Wk }; A[N ] |Wk , Q) [k]

(124) [k]

=I(Wi \ {Wk }; A[N ] |Wk , Q) + I(Wj \ {Wk }; A[N ] |Wi \ {Wk }, Wk , Q)

[k] [k] ≥I(Wi \ {Wk }; Ai |Wk , Q) + I(Wj \ {Wk }; Aj |Wi \ {Wk }, Wk , Q) [k] [k] [k] [k] =H(Ai |Wk , Q) − H(Ai |Wi , Q) + H(Aj |Wi , Q) − H(Aj |Wi , Wj , Q) [k ]

[k ]

=H(Ai 1 |Wk , Q) + H(Aj 2 |Wi , Q) [k ]

[k ]

≥H(Ai 1 |W \ {Wk1 }, Q) + H(Aj 2 |W \ {Wk2 }, Q).

(125) (126) (127) (128) (129)

Let {k1 } = Ii ∩In1 , and {k2 } = Ij ∩In2 for some n1 , n2 ∈ [N], n1 , n2 6= i, j. In particular, let k1 = In1 (mn1 ) and k2 = In2 (mn2 ), where mn1 ∈ [deg(n1 )] and mn2 ∈ [deg(n2 )]. Notice that, [k ] for k ′ = In1 (mn1 − 1), it holds that H(An11 |W \ {Wk1 }, Q) is one of the terms on the right hand side of the inequality bounding Dk′ − L. Similarly, for k ′′ = In2 (mn2 − 1), it holds that [k ] H(An22 |W \ {Wk2 }, Q) is one of the terms on the right hand side of the inequality bounding Dk′′ − L. Such k ′ and k ′′ exist because the degrees of n1 and n2 are at least 2. Summing the inequality over all k yields KL on the right hand side, by applying Lemma 3 to each pair of answers with the same index.

Generalizing to Multigraphs

In this section, we extend the local PIR results from simple graphs to r-multigraphs, where r ≥ 1. We begin with the problem setting and introduce the new notations associated with this extension. Next, we state the results in Section 6.2, followed by their proofs in Section 6.3.

6.1

Problem Setting

In the simple graph G = (V, E), let Wk , k ∈ [K ′ ] be the unique message stored at servers i, j ∈ [N], where |E| = Kr = K ′ . Then, the r-multigraph version of G is represented as G(r) = (V, E (r) ), where E (r) denotes the set of edges indexed as {(ℓ, 1), (ℓ, 2), . . . , (ℓ, r), ℓ ∈ [K ′ ]}. Accordingly, for the multigraph G(r) -based setting, let the set Wi,j = Wi ∩ Wj = {Wk,1, Wk,2 , . . . , Wk,r } denote the set of r unique messages stored at both servers i and j. Let θ = (s, τ ), where s ∈ [K ′ ] and τ ∈ [r], be the desired message index which is picked uniformly at random from [K ′ ] × [r]. The index set In , here, is the set of r deg(n) tuples (ℓ, τ ), such that Wℓ,τ ∈ Wn for all τ ∈ [r]. Under this setting, the local PIR problem on G(r) requires satisfying the information27

Multigraph type (r) Path PN (r) Cyclic CN (r)

Complete KN (r)

Star SN

Complete, balanced (r) bipartite K N , N 2

Thm. 8

Thm. 9

N −1 (2 − 21−r )−1 2N −3 1 (2 − 21−r )−1 2

√1 (2 − 21−r )−1 2 N −1 √ 1 (2 − 21−r )−1 N −1 √ 1 (2 − 21−r )−1 2N

1 (2 − 21−r )−1 N −1 2 (2 − 21−r )−1 N 2 (2 − 21−r )−1 N

RP IR 2 (2 − 21−r )−1 N −r −1

(1 − 2 )

max

1 N −21−r 2 (2 − 21−r )−1 N 1

1 1 , N +1 N (1+2−r )

N 1−2−r 2

Table 10: Achievable local PIR rates and best-achievable PIR rates for common multigraph families. theoretic constraints in (3),(5)-(7). The rate R(G(r) ) and capacity C(G(r) ) of the multigraphbased local PIR setting follow the same deﬁnitions as the simple graph case, i.e., when r = 1.

6.2

Results

The achievable local rates are summarized in Table 10, and compared against the corre(r) (r) (r) sponding best-known PIR rates, which for PN and SN are from [40], for CN are from [40] (r) (r) and [42], respectively, for KN is from [41] and for K N , N is from [42]. It is worth noting 2 2 that, extending the bipartite graphs scheme (Section 4.4) directly, causes the local PIR rate of G(r) to decrease linearly as 1r . Thus, the rate vanishes to 0 as r → ∞, and the scheme is far from optimal. Fortunately, the other proposed schemes on simple graphs extend well to the respective multigraphs G(r) , yielding capacity lower bounds that are bounded above zero. As established in the following, the local PIR capacity is a decreasing function of r, similar to its PIR counterpart. The ﬁrst result connects the local PIR rate of graphs to that of r-multigraphs, provided that the local PIR scheme satisﬁes the symmetric retrieval property (SRP) [40] as deﬁned next. Deﬁnition 4 (Symmetric Retrieval Property (SRP) [40]) A graph-based PIR scheme is said to satisfy the symmetric retrieval property if, for any k, the number of symbols of [k] [k] Wk retrieved from each of the servers storing Wk , is equal. Equivalently, H(Ai |Qi , Wi \ [k] [k] k) , if Wk is replicated on servers i and j. {Wk }) = H(Aj |Qj , Wj \ {Wk }) = H(W 2 Remark 9 It can be veriﬁed that, by Theorem 3, one obtains a local PIR scheme that satisﬁes SRP, for any graph G. Also, for edge-transitive graphs, that are regular, i.e., deg(i) = deg(j) = d, Theorem 2 yields a local PIR scheme that satisﬁes SRP. We apply this deﬁnition and claim that there exists a local PIR scheme on any multi graph establishing a lower bound on C G(r) , using the construction approach of [40, Section IV.A.]. 28

Theorem 8 A local PIR scheme on a simple graph G satisfying the SRP condition, resulting in rate R(G) can be adapted to obtain a local PIR scheme on its multigraph version, G(r) . The resulting capacity lower bound is given by C(G(r) ) ≥ R(G) 2 − 21−r

−1

(130)

The scheme achieving the rate in (130) requires the subpacketization level L to grow by a factor of 2r−1 , which may be impractical for smaller message sizes. In the next theorem, we propose another capacity lower bound for general multigraphs with minimal subpacketization, i.e., L = 1. Theorem 9 For the r-multigraph version G(r) of graph G = (V, E) with |V | = N and |E| = Kr , the capacity of local PIR is lower-bounded as C(G(r) ) ≥ K ·

r(1 − 2−r )

deg(n)2

n∈V

!−1

(131)

Remark 10 In relation to Theorem 5, if the corresponding achievable rate for G is given by ′ R(G), the lower bound (131) also satisﬁes C(G(r) ) ≥ (1−2−r ) PK deg(n)2 = R(G)(2−21−r )−1 . n∈[N]

For the multigraph version of graphs in Table 5, the local PIR rates in the second, third and ﬁfth columns multiplied by (2 − 21−r )−1 are all achievable, yielding lower bounds on C(G(r) ). Further, the capacity C(G(r) ) cannot increase as r increases, because a higher r implies stricter local privacy constraint. This implies that C(G) is a trivial upper bound for C(G(r) ). Next, we present the upper and lower capacity bounds for the cyclic (Theorem 10) and path (Theorem 11) multigraphs. Although there is a gap between the bounds, they improve upon the trivial upper bound for r > 1. (r)

Theorem 10 (Capacity bounds for CN ) For the r-multigraph version of cyclic graphs, (r) CN , with r > 1, the local PIR capacity is bounded as 1 1 (r) ≤ C(CN ) ≤ . 1−r 2(2 − 2 ) 3 − 21−r

(132)

Remark 11 Note that, the lower and upper bounds exactly match for r = 1, while the optimality gap for r > 1, expressed as the ratio of upper and lower bounds, settles at 34 as r → ∞. Moreover, the diﬀerence between the upper and lower bounds increases upto the 1 = 0.083 at asymptotic r. maximum value of 12 (r)

Remark 12 In contrast, the PIR capacity for CN is bounded as max

1 2 , 1−r (N + 1)(2 − 2 ) N(1 − 2−2r )

(r)

≤ CP IR (CN ) ≤

1 , N − (N − 1)2−r

(133)

by [40] and [42], respectively, where the lower bound in (132) exceeds the upper bound in (133) for N ≥ 4. (r)

Theorem 11 (Capacity bounds for PN ) For the r-multigraph version of path graphs, (r) PN , with r > 1, the local PIR capacity is bounded as N −1 N −1 (r) ≤ C(P . ) ≤ N (2N − 3)(2 − 21−r ) (N − 3)(3 − 21−r ) + 2

(134)

−3) which is approximately 43 for asympRemark 13 As r → ∞, the optimality gap is 2(2N 3(N −3) totically large N. (r)

Remark 14 The PIR capacity for PN [40] is known exactly for even N as (r)

CP IR (PN ) =

2 , N(2 − 21−r )

(135)

while for odd N it is bounded as 2 2 (r) ≤ C (P . ) ≤ P IR N N(2 − 21−r ) (N − 1)(2 − 21−r )

(136)

The lower bound in (134) is strictly greater for N ≥ 4, and equal for N = 3.

6.3

Proofs

6.3.1

Proof of Theorem 8

Let the local PIR scheme Π on G, satisfying SRP, require the message subpacketization to P ′ be L′ (which is even), and the total download cost to be D ′ = K k=1 Dk . We apply the r-stage algorithm proposed in [40] to such a scheme, and show that it yields a valid local PIR scheme on G(r) as described next. The user privately permutes the L = 2r−1 L′ symbols of every message independently and uniformly at random, with Wℓ,τ (m) representing the mth permuted symbol of Wℓ,τ , ℓ ∈ [K ′ ], τ ∈ [r]. For each server n, we partition the index set In into disjoint subsets In,1 , . . . , In,r , where for each τ ∈ [r], In,τ = {(ℓ, τ ) : Wℓ,τ ∈ Wn }.

(137)

Without loss of generality, assume that the desired message index is θ = (k, 1), where Wk,1 ∈ Wi,j , with i < j. Throughout the scheme, the user communicates only with the servers in Vk deﬁned in (15) and queries for the message symbols of Wi ∪ Wj . For the purpose of scheme description, we also consider the index sets Ek,1 , . . . , Ek,r , where for each τ ∈ [r], Ek,τ = {(ℓ, τ ) ∈ Ii,τ ∪ Ij,τ } ⊆ E (r) , 30

(138)

which is the τ th set of edges incident with the nodes in Vk . The scheme proceeds in r stages as described next. In the ﬁrst stage, we apply the scheme Π to the messages corresponding to Ek,1 to obtain the desired message symbols Wk,1 [1 : L′ ] and to Ek,2 , . . . , Ek,r to retrieve the interference message symbols {Wk,τ [1 : L′ ], τ ∈ [2 : r]}. That is, Π is applied r times to disjoint message subsets. Further, assume that the answers received from server i involve Wk,τ [1 : L′ /2], while the answers received from server j involve Wk,τ [L′ /2 + 1 : L′ ]. In the second stage, we consider all possible 2-subsets of {Ek,1 , . . . , Ek,r }. For each subset {Ek,τ1 , Ek,τ2 }, we apply Π to message sums given by {Wℓ,τ1 + Wℓ,τ2 : (ℓ, τ1 ) ∈ Ek,τ1 , (ℓ, τ2 ) ∈ Ek,τ2 }.

(139)

r r−1 Out of these sums, r−1 contain W as a term, and − (r − 1) = do not. For k,1 1 2 2 a ﬁxed subset {Ek,1 , Ek,τ }, τ ∈ [2 : r], we modify the queries of Π such that, the answers from server i involve Wk,1[(τ − 1)L′ + 1 : (τ − 1)L′ + L′ /2] + Wk,τ [L′ /2 + 1 : L′ ], while the answers from server j involve Wk,1 [(τ − 1)L′ + L′ /2 + 1 : τ L′ ] + Wk,τ [1 : L′ /2]. From here, we decode the (r − 1)L′ desired message symbols, Wk,1[L′ + 1 : rL′ ], by utilizing the side information from the ﬁrst stage. Let the subsets that do not contain Ek,1 have a ﬁxed ordering. Further, let {Ek,τ1 , Ek,τ2 }, τ1 6= τ2 , τ1 , τ2 ∈ [2 : r], be such that Ek,τ1 and Ek,τ2 occur at the t1 th and t2 th position (t1 , t2 ∈ r−1 ), respectively, among the ordered 2 subsets. Then, we assume that the answers from server i involve Wk,τ1 [(t1 − 1)L′ + 1 : (t1 − 1)L′ + L′ /2] + Wk,τ2 [(t2 − 1)L′ + 1 : (t2 − 1)L′ + L′ /2], while the answers from server j involve Wk,τ1 [(t1 − 1)L′ + L′ /2 + 1 : t1 L′ ] + Wk,τ2 [(t2 − 1)L′ + L′ /2 + 1 : t2 L′ ]. These sums of symbols act as side information for the next stage. For a general stage 3 ≤ σ ≤ r − 1, we consider all possible σ-subsets of {Ek,1, . . . , Ek,r }. For a ﬁxed subset {Ek,τ1 , . . . , Ek,τσ }, we apply Π to message sums given by {Wℓ,τ1 + . . . + Wℓ,τσ : (ℓ, t) ∈ Ek,t ∀t ∈ {τ1 , . . . , τσ }},

(140)

Pσ−1 r−1 ′ ′ Pσ−1 r−1 ′ r−1 to retrieve the symbol indices of Wk,1 . First, s=1 s−1 L + 1 : s=1 s−1 L + σ−1 L r−1 for the σ−1 subsets with τ1 = 1, and τ2 , . . . , τσ ∈ [2 : r], let the respective subsets have a ﬁxed ordering. Corresponding to the tth subset given by, {Ek,1, Ek,τ2 , . . . , Ek,τσ }, the answers recover the message symbols Wk,1

" σ−1 X r − 1 s=1

s−1

′

L + (t − 1)L + 1 :

σ−1 X r−1 s=1

s−1

′

L + tL ,

(141)

added to the (σ − 1)-sum σ X l=2

Wk,τl [(Uτl − 1)L′ + 1 : Uτl L] , 31

(142)

where [(Uτ2 − 1)L′ + 1 : Uτ2 L′ ], . . . , [(Uτσ − 1)L′ + 1 : Uτσ L′ ] in (142) are the symbols of the (σ − 1) message sums that were retrieved in stage (σ − 1), corresponding to the subset {Ek,τ2 , . . . , Ek,τσ }, as side information. We follow the convention that the ﬁrst L′ /2 symbols of (141), and the latter L′ /2 symbols of (142) are contributed by server i, while the latter L′ /2 symbols of (141), and the ﬁrst L′ /2 symbols of (142) are contributed by server j. If τ1 6= 1, we ﬁx the ordering of the r−1 subsets. For a ﬁxed subset {Ek,τ1 , . . . , Ek,τr }, let tl σ be the position of τl in this subset. Then, the answers recover the message symbols σ X l=1

Wk,τl [(Vτl − 1)L′ + 1 : Vτl L′ ],

(143)

P r−1 ′ where Vτl = σ−1 s=1 s−1 + (tl − 1). In every such sum, the ﬁrst L /2 symbols are contributed by server i, while the last L′ /2 symbols are contributed by server j. In stage r, no new side information is created, and the remaining L′ symbols of Wk,1, i.e., Pr−1 r−1 ′ r−1 ′ Wk,1 L , are decoded by utilizing the side information from stage s=1 s−1 L + 1 : 2 P r − 1. Thus, Wk,1 is decoded by downloading Dk,1 = rt=1 rt D ′ message symbols. The same download cost is required for all τ ≥ 2, yielding the rate Pr

τ =1

KL PK ′

k=1 Dk,τ

KL′ 2r−1 rK ′ (2r − 1)D ′

= RΠ (G)(2 − 21−r )−1 .

(144) (145)

In every stage of the scheme, all possible sums of message subsets are involved, irrespective of the desired message index. When θ = k, each invocation of the scheme Π is locally private against the concerned servers i and j. Finally, following the construction in [40], the scheme takes care that the interference message symbols retrieved from server i are queried in the subsequent stage from server j, summed with the desired message symbols, and vice versa. Next, we illustrate the scheme by extending the example on the bipartite graph K2,3 in (2) Section 4.3 to K2,3 for θ = (1, 1), by querying the servers 1 to 5. Let the 12 symbols of each Wk,τ , k ∈ [6], τ ∈ [2] be permuted independently and uniformly at random, and be labeled using the same letters as the previous example, without and with the prime symbol (′ ) when τ = 1, and τ = 2, respectively. From the scheme presented in Table 11, the user retrieves 12 = 27 . a1 , . . . , a12 , yielding the rate 42 6.3.2

Proof of Theorem 9

The proof follows the ideas of Theorem 5. Assume that the set of indices at server n is S speciﬁed as In = τ ∈[r] {ℓ1,τ , ℓ2,τ , . . . , ℓdeg(n),τ }, where ℓ1,τ < ℓ2,τ < . . . < ℓdeg(n),τ for all

stage 1

server 1 a1 , b1 , c1 a2 + b2 , a3 + c2 , b3 + c3 a′1 , b′1 , c′1 ′ ′ a2 + b2 , a′3 + c′2 , b′3 + c′3 a7 + a′4 , b7 + b′7 , c7 + c′7 a8 + b8 + a′5 + b′8 a9 + c8 + a′6 + c′8 b9 + c9 + b′9 + c′9

server 2 d3

server 3 a4 , a5 , d1 , d2 a6 + d3 ′ a4 , a′5 , d′1 , d′2 a′6 + d′3 a10 + a′1 , a11 + a′2 d7 + d′7 , d8 + d′8 a12 + d9 + a′3 + d′9

d′3 d9 + d′9

server 4 b2

server 5 c2

b′2

c′2

b8 + b′8

c8 + c′8

(2)

Table 11: Retrieval scheme for K2,3 . τ ∈ [r]. Accordingly, let the messages at server n be arranged in the form of the matrix 

  Wn =   

Wℓ1 ,1 Wℓ2 ,1 .. .

Wℓ1 ,2 Wℓ2 ,2 .. .

... ... .. .



Wℓ1 ,r Wℓ2 ,r .. .

Wℓdeg(n) ,1 Wℓdeg(n) ,2 . . . Wℓdeg(n) ,r

  .  

(146)

The user generates K bits hs,τ , (s, τ ) ∈ [K ′ ] × [r] independently, where each hs,τ is picked uniformly at random from {0, 1}. Let these bits be arranged into n matrices as 

hℓ1 ,1 hℓ2 ,1 .. .

hℓ1 ,2 hℓ2 ,2 .. .

... ... .. .

hℓ1 ,r hℓ2 ,r .. .



    . Hn =      hℓdeg(n) ,1 hℓdeg(n) ,2 . . . hℓdeg(n) ,r

(147)

Let θ = (k, 1) with Wk,1, . . . , Wk,r stored at servers i and j. Further, let [Wk,1 , . . . , Wk,r ] be the pth row of Wi , and the mth row of server j. Like the simple graph scheme, only servers i and j (i < j) receive a query given by [k,1]

= Hi ,

where Hi (p, :) = Hj (m, :) = hk,1 hk,2

[k,1]

= Hj + em e⊤ 1,

(148)

i . . . hk,r , and em e⊤ 1 is a deg(j) × r matrix of all [k,1]

zeros with a 1 at the (m, 1)th coordinate. The answer An [k,1] vector whose νth entry An (ν) is given by

returned by servers i and j is a

 [k,1] Q[k,1] ⊤ ⊤ n (ν, :)Wn (ν, :) , Qn (ν, :) 6= 0 , [k,1] An (ν) = [k,1] ∅, Qn (ν, :) = 0⊤ ,

(149)

where 0 is the r-length column vector of all zeroes. The corresponding download cost Dk,1 [k,1] [k,1] is given by the total length of answers Ai and Aj , averaged over all realizations of 33

{hℓ,τ , ℓ ∈ Ii ∪ Ij , τ ∈ [r]} ∈ {0, 1}r(deg(i)+deg(j)) . First, we compute the average answer length for the queries generated from hk,1 , . . . , hk,r , [k,1] [k,1] which correspond to Qi (p, :) and Qj (m, :), for server i and server j, respectively. A [k,1] single bit, i.e., Wk,1 is returned either by server j alone, if the pth query row, Qi (p, :) = [k,1] ⊤ Hi (p, :) = 0⊤ or by server i alone, if the mth query row, Qj (m, :) = Hj (m, :) + e⊤ 1 = 0 . Notice that each of these events occurs with probability 2−r . Otherwise, each of the servers [k,1] i and j returns a single bit, i.e., 2 bits in total, whenever both the query vectors Qi (p, :) [k,1] and Qj (m, :) are non-zero. This occurs with probability 1 − 21−r . Next, for the queries generated from {hℓ,τ , ℓ ∈ Ii ∪Ij \{k}, τ ∈ [r]}, let Xi ∈ [0 : deg(i)−1] and Xj ∈ [0, deg(j)−1] be the number of rows in Hi and Hj , respectively, that are not 0⊤ , excluding the row of [hk,1 , . . . , hk,r ]. Picking any such row from Hi and Hj (say, the νth row), we have P Hi (ν, :) 6= 0⊤ = 1 − P Hi (ν, :) = 0⊤ = 1 − 2−r , P Hj (ν, :) 6= 0⊤ = 1 − P Hj (ν, :) = 0⊤ = 1 − 2−r .

(150) (151)

Since the random variables are independent, the entries of the rows are mutually independent. This yields X

Xi =

ν∈[deg(i)]\{p}

Xj =

1 Hi (ν, :) 6= 0⊤ ,

ν∈[deg(j)]\{m}

1 Hj (ν, :) 6= 0⊤ .

(152) (153)

Thus, we have Dk,1 = 1 · 21−r + 2 · (1 − 21−r ) + E [Xi ] + E [Xj ]

= 2 − 21−r + (deg(i) − 1)(1 − 2−r ) + (deg(j) − 1)(1 − 2−r ) = (1 − 2−r ) (deg(i) + deg(j)) .

(154) (155) (156)

The expression in (156) for Dk,τ holds for all τ ∈ [r]. Summing over k and τ yields the total download as ′

K X r X k=1 τ =1

′

Dk,τ =

K X k=1

r(1 − 2−r )(deg(i) + deg(j))

= r(1 − 2−r ) = r(1 − 2−r )

(157)

(deg(i) + deg(j))

(158)

deg(n)2 ,

(159)

{i,j}∈E

n∈[N ]

which gives the desired result. For Theorems 10 and 11, the lower bounds follow from Theorem 8. For the upper bounds, 34

we need the following lemma, which is a modiﬁed form of [40, Lemma 23], relaxed for local privacy, with respect to the indices θ for which this constraint needs to be satisﬁed. Lemma 4 (Lemma 23, [40]) For any two servers i, j with {i, j} ∈ E, and for any θ ∈ Ii ∩ Ij , a local PIR scheme on the r-multigraph G(r) , satisﬁes [θ] [θ] H(Ai |W \ Wi,j , Q) + H(Aj |W \ Wi,j , Q) ≥ L 2 − 21−r .

(160)

To prove the upper bounds, we ﬁnd a lower bound on the download cost for each desired index, and deviate slightly from the simple graph case as follows. Starting with a ﬁxed index, θ = (s, τ ), where s ∈ [N], τ ∈ [r], we obtain [s,τ ]

Ds,τ ≥ L + I(W \ {Ws,τ }; A[N ] |Ws,τ , Q)

(161) [s,τ ]

= L + I(W \ Ws,s+1 , Ws,s+1 \ {Ws,τ }; A[N ] |Ws,τ , Q)

(162)

[s,τ ]

= L + I(Ws,s+1 \ {Ws,τ }; A[N ] |Ws,τ , Q) + I(W \ Ws,s+1; A[N ] |Ws,s+1, Q)

(163)

≥ L + I(W \ Ws,s+1 ; A[N ] |Ws,s+1, Q),

(164)

[s,τ ]

where (164) holds by setting the ﬁrst term in (163) to zero. For r > 1, this dropped term contributes to the gap between the lower and upper bounds. The proofs of the latter (Theorems 10 and 11) appear next. 6.3.3

Proof of Theorem 10

The storage at server n ∈ [N] is given by the 2r messages, Wn = Wn−1,n ∪ Wn,n+1

(165)

= {Wn−1,τ , Wn,τ , τ ∈ [r]},

(166)

where the indices are added and subtracted modulo N. The second term in (164) can be lower-bounded as [s,τ ]

I(W \ Ws,s+1; A[N ] |Ws,s+1, Q)

[s+1,τ ]

] ≥ I(Ws−1,s ; A[s−1,τ |Ws,s+1, Q) + I(Ws+1,s+2 ; As+1 s [s+1,τ ]

] = H(A[s−1,τ |Ws,s+1 , Q) + H(As+1 s

|Ws,s+1, Ws−1,s , Q)

[s+1,τ ] ] ≥ H(A[s−1,τ |W \ Ws−1,s , Q) + H(As+1 |W \ Ws,s+1, Q). s

(167) (168) (169)

Now, summing over all s, τ , following the steps in Section 5.1 and using Lemmas 1, 2 and 4, we obtain N X r X s=1 τ =1

Ds,τ ≥ NrL + Nr(2 − 21−r )L 35

(170)

= NrL(3 − 21−r ). 6.3.4

(171)

Proof of Theorem 11 (r)

Recall that the storage of PN is

Wn =

    W1 = {W1,τ , τ ∈ [r]},

n = 1,

Wn−1,n ∪ Wn,n+1 = {Wn−1,τ , Wn,τ , τ ∈ [r]}, n ∈ [2 : N − 2],    WN −1 = {WN −1,τ , τ ∈ [r]}, n = N − 1.

(172)

Starting from (164), and following the arguments in Section 5.2, we lower bound the interference for all τ ∈ [r] as [s,τ ]

I(W \ Ws,s+1; A[N ] |Ws,s+1, Q)  [s+1,τ ]    H(As+1 |W \ Ws+1,s+2 , Q), ≥

s = 1,

[s−1,τ ] [s+1,τ ] H(As |W \ Ws−1,s , Q) + H(As+1 |W \ Ws+1,s+2 , Q),

   ] H(A[s−1,τ |W \ Ws−1,s , Q), s

s ∈ [2 : N − 2],

(173)

s = N − 1.

Summing over all (s, τ ) ∈ [N − 1] × [r], N −1 X r X s=1 τ =1

Ds,τ ≥ (N − 1)rL + (N − 3)rL(2 − 21−r )

(174)

= rL N − 3)(3 − 21−r + 2 .

(175)

Conclusion

In this paper, we studied graph-based private information retrieval from the perspective of local privacy for simple graphs and multigraphs. On one hand, fully-replicating the database at all servers improves the capacity with the increased number of servers. On the other hand, with the massive amount of data, realizing full-replication becomes more and more expensive and essentially untenable. Therefore, settling for a compromise of (hyper)graph replicated storage for PIR is a judicious model to avoid extremely large replication costs. However, the original deﬁnition of PIR under this setup is too conservative and causes degradation in capacity as more servers are included in the system. This is because inclusion of servers inevitably adds more messages to the PIR system, further amplifying the privacy requirement. To circumvent this issue, our local privacy formulation oﬀers a reasonable privacy deﬁnition, where the retrieval of a message is hidden from a server if and only if that message is stored in that sever. The relaxation of privacy yields a natural improvement over the communication eﬃciency 36

of PIR, and the results are more encouraging than those of the original treatment of graphreplicated PIR. Moreover, as N increases, the local PIR capacity decays at a slower rate than the standard PIR capacity. For simple graphs, we proposed capacity lower bounds that √ are at least O( N ) times superior to the rates of standard PIR, whereas cyclic and path graphs exhibit O(N) times improvement in the capacity. For multigraphs, the rates achieved through our proposed schemes are the rates of the respective simple graphs, multiplied by the factor (2 − 21−r )−1 . Further work is needed to characterize the exact/approximate capacity of graphs other than star, cyclic and path, to understand the limits of rate improvement of local PIR against PIR. Similarly, in the domain of multigraphs, characterizing the capacity bounds of most multigraphs remains open.

References [1] B. Chor, E. Kushilevitz, O. Goldreich, and M. Sudan. Private information retrieval. Journal of the ACM, 45(6):965–981, November 1998. [2] A. Beimel and Y. Ishai. Information-theoretic private information retrieval: A uniﬁed construction. In Springer ICALP, July 2001. [3] A. Beimel, Y. Ishai, E. Kushilevitz, and J-F. Raymond. Breaking the O(n1/(2k−1) ) barrier for information-theoretic private information retrieval. In IEEE FOCS, November 2002. [4] D. Woodruﬀ and S. Yekhanin. A geometric approach to information-theoretic private information retrieval. In IEEE CCC, June 2005. [5] A. Beimel and Y. Stahl. Robust information-theoretic private information retrieval. Journal of Cryptology, 20(3):295–321, 2007. [6] Z. Dvir and S. Gopi. 2-server PIR with subpolynomial communication. Journal of the ACM, 63(4):1–15, 2016. [7] H. Sun and S. A. Jafar. The capacity of private information retrieval. IEEE Trans. Inf. Theory, 63(7):4075–4088, March 2017. [8] C. Tian, H. Sun, and J. Chen. Capacity-achieving private information retrieval codes with optimal message size and upload cost. IEEE Trans. Inf. Theory, 65(11):7613–7627, November 2019. [9] N. B. Shah, K. V. Rashmi, and K. Ramchandran. One extra bit of download ensures perfectly private information retrieval. In IEEE ISIT, June 2014. [10] R. Tajeddine, O. Gnilke, and S. El Rouayheb. Private information retrieval from MDS coded data in distributed storage systems. IEEE Trans. Inf. Theory, 64(11):7081–7093, March 2018. 37

[11] H. Sun and S. A. Jafar. Private information retrieval from MDS coded data with colluding servers: Settling a conjecture by Freij-Hollanti et al. IEEE Trans. Inf. Theory, 64(2):1000–1022, December 2017. [12] 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. [13] K. Banawan and S. Ulukus. The capacity of private information retrieval from coded databases. IEEE Trans. Inf. Theory, 64(3):1945–1956, January 2018. [14] 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. [15] H. Sun and S. A. Jafar. The capacity of symmetric private information retrieval. IEEE Trans. Inf. Theory, 65(1):322–329, June 2018. [16] 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. [17] 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. [18] 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. [19] 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. [20] 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. [21] 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. [22] M. Nomeir, S. Vithana, and S. Ulukus. Asymmetric X-secure T -private information retrieval: More databases is not always better. In CISS, March 2024. [23] M. Nomeir, A. Aytekin, and S. Ulukus. The capacity of semantic private information retrieval with colluding servers. In IEEE GLOBECOM, December 2025. 38

[24] 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. [25] 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. [26] 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. [27] 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. [28] M. Nomeir, A. Aytekin, and S. Ulukus. The asymptotic capacity of Byzantine symmetric private information retrieval and its consequences. In IEEE ISIT, June 2025. [29] S. Song and M. Hayashi. Capacity of quantum private information retrieval with multiple servers. IEEE Transactions on Information Theory, 67(1):452–463, 2021. [30] M. Allaix, S. Song, L. Holzbaur, T. Pllaha, M. Hayashi, and C. Hollanti. On the capacity of quantum private information retrieval from mds-coded and colluding servers. IEEE Journal on Selected Areas in Communications, 40(3):885–898, 2022. [31] Y. Lu and S. A. Jafar. Quantum X-secure T -private information retrieval from MDS coded storage with unresponsive and Byzantine servers. IEEE Jour. Sel. Areas Inf. Theory, 6:59–73, 2025. [32] 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. Inf. Theory, 72(6):4312–4328, 2026. [33] A. Heidarzadeh, S. Kadhe, S. El Rouayheb, and A. Sprintson. Single-server multimessage individually-private information retrieval with side information. In IEEE ISIT, July 2019. [34] A. Heidarzadeh, F. Kazemi, and A. Sprintson. The role of coded side information in single-server private information retrieval. IEEE Trans. Inf. Theory, 67(1):25–44, October 2021. [35] N. Raviv, I. Tamo, and E. Yaakobi. Private information retrieval in graph-based replication systems. IEEE Trans. Inf. Theory, 66(6):3590–3602, November 2019. [36] K. Banawan and S. Ulukus. Private information retrieval from non-replicated databases. In IEEE ISIT, July 2019.

[37] Z. Jia and S. A. Jafar. On the asymptotic capacity of X-Secure T -Private information retrieval with graph-based replicated storage. IEEE Trans. Inf. Theory, 66(10):6280– 6296, July 2020. [38] 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. [39] Y. Yao and S. A. Jafar. The capacity of 4-star-graph PIR. In IEEE ISIT, June 2023. [40] 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. [41] V. Shanbhag and P. Krishnan. Private information retrieval for graph-based replication with minimal subpacketization, 2026. Available online at arXiv:2601.09957. [42] G. Ge, H. Wang, Z. Xu, and Y. Zhang. Private information retrieval over graphs, 2025. Available online at arXiv:2509.26512. [43] 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. [44] S. Meel and S. Ulukus. Symmetric private information retrieval (SPIR) on graph-based replicated systems. In IEEE GLOBECOM, December 2025. [45] S. Meel and S. Ulukus. Eﬀect of full common randomness replication in symmetric PIR on graph-based replicated systems. In IEEE ICC, May 2026. [46] 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. [47] I. Samy, R. Tandon, and L. Lazos. On the capacity of leaky private information retrieval. In 2019 IEEE ISIT, 2019. [48] T. Guo, R. Zhou, and C. Tian. On the information leakage in private information retrieval systems. IEEE Trans. Inf. Forensics Security, 15:2999–3012, March 2020. [49] C. Qian, R. Zhou, C. Tian, and T. Liu. Improved weakly private information retrieval codes. In 2022 IEEE ISIT, pages 2827–2832, 2022. [50] H.-Y. Lin, S. Kumar, E. Rosnes, A. G. i Amat, and E. Yaakobi. Multi-server weaklyprivate information retrieval. IEEE Trans. Inf. Theory, 68(2):1197–1219, 2021. [51] S. Vidya, C. Anand, and P. Krishnan. Weak private information retrieval for graphbased storage. 2026. Available online at arXiv:2607.21014. 40

Local Private Information Retrieval for Graph-Based Replicated Systems

Analyze & explore related research in Conceptio

Related documents